[Algorithm] 소수 구하기 알고리즘 3 (에라토스테네스의 체)

소수 판별 알고리즘 3 (에라토스테네스의 체)

알고리즘 목적

1부터 어떠한 수까지 중에 소수인지 아닌지를 판별하는 알고리즘

 

에라토스테네스의 체

: 소수를 구하는 대표적인 방법 중 하나로 k = 2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수를 제외시키는 방법

에라토스테네스의 체

알고리즘 방법

1. k = 2부터 (2부터 소수의 시작임.) √N 이하까지 반복 ( = 소수 판별 알고리즘 2)
2. √N 이하까지 k를 제외한 k의 배수를 제외시키기!! ( 배수를 제외시킨다는 것은 그들은 약수가 있다는 것이기 때문에 소수가 아닌 것.)
3. 나머지가 모두 소수임.

*시간복잡도 : N㏒N

실제 알고리즘 구현 (Java)

import java.util.Scanner;
 
public class Prime_3 {
 
    public static boolean[] prime;

	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		
		make_prime(N);
 
		for(int i = 0; i < prime.length; i++) {
			if(prime[i] == false) {	// 소수(false)일 경우 출력
				System.out.println(i);
			}
		}
	}
  
	public static void make_prime(int N) {
		
		prime = new boolean[N + 1];	// 0 ~ N
 
		/*
		소수가 아닌 index = true
		소수인 index = false
		*/
		
		if(N < 2) {
			return;
		}
        
		prime[0] = prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(N); i++) {
        
			// 이미 체크된 배열이면 다음 반복문으로 skip
			if(prime[i] == true) {
				continue;
			}
        
			// i 의 배수들 (j+i) 걸러주기 위한 반복문
			for(int j = i * i; j < prime.length; j = j+i) {
				prime[j] = true;
			}
		}
 
	}
 
}