Go로 소수 구하기 with 백준 1929

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

위 문제는 소수 구할 때 자주 쓰이는 알고리즘인 에라토스테네스의 체를 사용하면 됩니다.

에라토스테네스의 체에 대한 설명은 나무 위키가 역시.. 잘 나와있습니다

 

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

 

과정 또한 예시가 있으므로 이해가 쉬우실 것입니다.

수열에서 소수의 배수들을 전부 제거해가면서 소수만을 남기는 알고리즘입니다.

 

package main

import (
	"fmt"
)

func main() {
	var min, max int
	numbers := make(map[int]bool)
	fmt.Scan(&min, &max)
	for i := 2; i <= max; i++ { // 1은 소수가 아니므로 제외합니다
		if numbers[i] { // 지금 수를 출력할 지 여부
			continue
		} else if i >= min {
			fmt.Println(i)
		}

		for k := 2 * i; k <= max; k += i {
			numbers[k] = true // k(소수)의 배수들은 출력 안함
		}
	}
}