소수를 출력해보자-2 (에라토스테네스의 체)

이전 글에서 소수를 출력한 적이 있지만 백준을 풀면서 에라토스테네스의 체를 알게 되었고 더 효율적이게 만들 수 있을거라는 생각이 들어 다시 포스팅합니다. 

에라토스테네스의 체란?

2의 배수 걸러네! 3의 배수 걸러네! 4의 배수 ? 어 너는 이미 걸러졋구나! 5의 배수 걸러네! 

만약 50까지의 소수를 찾는다면 7의 배수까지만 걸러네면 된다 

7*7<50<8*8 이기 때문에 --> 이 점을 이용하여 조금이라도 빨리 소수를 걸러내보자!

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		
		boolean arr[] = new boolean[a+1];
		for(int i=0;i<a;i++) {
			arr[i]=true;
		}
		arr[0] = false;
		arr[1] = false;
		int num = (int)Math.sqrt(a);
		for(int i=2;i<=num;i++) {
			if(arr[i]) {
				for(int j=i*i;j<=a;j=j+i) {
					arr[j]=false;
				}
			}
		}
		for(int i=0;i<=a;i++) {
			if(arr[i]) {
				System.out.println(i);
			}
		}
    }
}

boolean arr에 입력받은 수에+1을 해준 이유는 직관성을 키우기 위해서이다. 배열은 0부터 시작하여 a-1에 끝나는데 1부터 시작하여 a에서 끝나는 것처럼 생각할 수 있다. 
따라서 arr0과 arr1은 false처리를 해주며 소수가 아닌 것을 확실히 해준다! 

1차 for 문은 입력수의 루트까지 돌린다.
2차 for문의 i*i를 하는 이유는 이전의 소수들은 이미 다 처리가 되었기 떄문이다. (이 부분은 i에 2를 대입해서 생각하면 편하다.)
2차for문에서 배수로 증가시키며 배수는 모두 소수가 아닌 취급을 해준다! 

 

끝!