김기헌
소수 구하기
소수 구하는 방법
•
2부터 n-1까지 나누어 보며 판단
•
2부터 root(n) {==sqrt(n)} 까지 나누어 보며 판단
2번의 방법으로도 충분히 빠른 시간 안에 소수인지 판별할 수 있다.
하지만 n이하의 수 중 소수를 찾으라는 문제가 나온다면 n개의 수를 모두 각각 소수인지 판별해야 하므로 많은 시간이 소요된다
에라토스테네스의 체
위와 같은 상황에 에라토스테네스의 체를 활용하면 효율적으로 n개의 수가 각각 소수인지 판별할 수 있다.
그렇다면 에라토스테네스의 체란?
2부터 Root(N)이하의 수까지 자기 자신을 제외한 배수를 모두 제외시키는 방법이다
2를 제외하고 2의 배수인 2, 4, 6 … n-1 or n
3을 제외하고 3의 배수인 3, 6, 9 … n-2 or n-1 or n
이렇게 지우고 남은 수는 소수가 되는 것이다.
public class PrimeNumber {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println(N을 입력하세요.(3이상)");
int N = scanner.nextInt();
boolean[] prime = new boolean[N + 1];
//boolean의 기본값은 false 이고 0과 1은 true로 미리 지정한다.
prime[0] = true;
prime[1] = true;
for (int i = 2; i * i <= N; i++) {//N의 제곱근까지
for (int j = i * i; j <= N; j += i){//자기 자신 제외
//i*i로 시작한 j는 i만큼 더하여 증가하기 때문에, j는 N보다 작은 i의 배수가 될 것.
//boolean의 기본값은 false 이기 때문에 배수에 속하는 것들을 true로 지정
prime[j] = true;
}
}
//false인 소수 출력
for (int i = 2; i <= N; i++) {
if (!prime[i]) {
System.out.println(i);
}
}
}
}
Java
복사
