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

소수

• 소수 : 약수가 해당 숫자 본인과 1만 존재하는 수를 의미한다. (영어로는 Prime Number)
• EX) 2, 3, 5, 7 ..... (짝수 중에선 2가 유일한 소수이다.)

 

에라토스테네스의 체

• 모든 자연수는 단 하나의 소수들의 곱으로 표현된다는 특징을 이용하여 일정 범위의 수들이 소수인지 여부를 판단하는 방법이다.
• 즉, 소수의 곱이 되는 수는 소수가 아닌 것을 이용하여 소수가 아닌 수들을 걸러나가는 방법이다.
• 2가지 방법이 있는 데 순서의 차이일 뿐 어느 것을 써도 무방하다.

 

1. 소수 구한 후 결과 반전

• boolean형 배열을 선언할 때는 초기값이 false로 채워져있기 때문에 우선 소수가 아닌 수들에 true를 해놓고 나중에 반전을 시키는 방법이다.

        int number = 10000;
        boolean isPrime[] = new boolean[number+1];

        for(int i = 2;i <= number;i++)
        {
            if(!isPrime[i])
            {
                for(int j = 2 * i;j <= number;j += i)
                    isPrime[j] = true;//소수가 아닌 수
            }
        }

		//결과 반전
        for(int i = 0;i <= number;i++)
            isPrime[i] = !isPrime[i];

 

2. 배열 true로 초기화

• boolean형 배열을 선언할 때 true로 초기화 시킨 후 소수가 아닌 수를 구하는 방법이다.
• 개인적으로는 이 방법이 덜 헷갈린다.

        int number = 10000;
        boolean isPrime[] = new boolean[number+1];
        
        //true로 초기화
        Arrays.fill(isPrime, true);

        for(int i = 2;i <= number;i++)
        {
            if(isPrime[i])
            {
                for(int j = 2 * i;j <= number;j += i)
                    isPrime[j] = false;//소수가 아닌 수
            }
        }