[java][algorithm]소수 구하기

소수 : 1과 자기자신으로만 나누어 떨어지는 정수

 

어떤 정수 n에 대하여 이중 for 문을 돌리면서 2부터 n-1까지 다른 정수로 나누어 떨어지지 않는지 확인 

 

코드 설명)

for 문에서 9를 만날때 9는 i가 3일 때 나누어 떨어지므로 break 

 

package chap02;
// 1,000 이하의 소수를 열거(버전 1)

class PrimeNumber1 {
    public static void main(String[] args) {
        int counter = 0;            // 나눗셈의 횟수

        for (int n = 2; n <= 1000; n++) {
            int i;
            for (i = 2; i < n; i++) {
                counter++;
                if (n % i == 0)        // 나누어떨어지면 소수가 아님
                    break;            // 더 이상의 반복은 불필요
            }
            if (n == i)                // 마지막까지 나누어떨어지지 않음
                System.out.println(n);
        }

        System.out.println("나눗셈을 수행한 횟수：" + counter);
    }
}

 

 

알고리즘개선 1

 

나눗셈 횟수를 줄이는 방법 ! 

 

n이 2또는 3으로 나누어 떨어지지 않으면 2*2 4 2*3인 6으로도 나누어 떨어지지 않는다.

따라서 n보다 작은 소수일때만 나눗셈 해보면 충분하다.

소수는 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다.

EX) n이 7일때 7보다 작은 소수 2,3,5 로 나누어 떨어지지 않으로 7은 소수!

n이 9일때 9보다 작은 소수 2,3,5,7 에서 3으로 나누어 떨어지므로 9는 합성수!   

 

코드 설명)

4이상의 짝수는 2로 나누어 떨어지므로 n의 값을 2씩 증가 시켜준다.

 

package chap02;
// 1,000 이하의 소수를 열거(버전 2)

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

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

        for (int n = 3; n <= 1000; n += 2) {    // 대상은 홀수만
            int i;
            for (i = 1; i < ptr; i++) {            // 이미 찾은 소수로 나누어 봄
                counter++;
                if (n % prime[i] == 0)            // 나누어떨어지면 소수가 아님
                    break;                        // 더 이상의 반복은 불필요
            }
            if (ptr == i)                        // 마지막까지 나누어떨어지지 않음
                prime[ptr++] = n;                // 소수라고 배열에 저장
        }

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

        System.out.println("나눗셈을 수행한 횟수：" + counter);
    }
}

 

알고리즘개선 2

소수는 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

 

package chap02;
// 1,000 이하의 소수를 열거(버전 3)

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

        prime[ptr++] = 2;                            // ２는 소수임
        prime[ptr++] = 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);
    }
}