1000 이하의 소수를 나열하기 (chap02/PrimeNumber3)

package chap02;

//1000 이하의 소수를 나열 (버전3)
public class PrimeNumber3 {

    public static void main(String[] args) {
        int counter = 0; //곱셈과 나눗셈의 횟수
        int ptr = 0; //찾은 소수의 개수
        int[] prime = new int[500]; //소수를 저정하는 배열

        prime[ptr++] = 2; //2는 소수임.
        prime[ptr++] = 3; //3는 소수임.

        for (int n = 5; n <= 1000; n += 2){ //조사대상은 홀수만
            boolean flag = false;
            for(int i = 1; prime[i] * prime[i] <= n; i++){
                counter += 2;
                if (n % prime[i] == 0){ //나누어떨어지면 소수가 아님
                    flag = true;
                    break; // 더이상의 반복은 불필요
                }
            }
            if (!flag){ //마지막까지 나누어떨어지지 않음
                prime[ptr++] = n; //소수를 배열로 저장
                counter++;
            }
        }

        for (int i = 0; i < ptr; i++) //찾은 ptr개의 소수를 출력
            System.out.println(prime[i]);

        System.out.println("곱셈과 나눗셈을 수행한 횟수 : " + counter);

    }
}

 

소수의 정의

• 자신과 1 이외의 어떤 정수로도 나누어떨어지지 않는 정수.
• 2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않음. 
• n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않음.