소수의 나열 [java]

다음은 1000 이하의 소수를 나열하는 코드이다.

public class Main {
    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); //78022
    }
}

그런데 n이 2나 3으로 나누어떨어지지 않으면 2*2나 2*3으로도 나누어떨어지지 않는다.

따라서 위의 코드는 불필요한 반복이 이루어지고 있다.

다시말해서 n이 소수인지 아닌지는 "n이 2 ~ n-1까지의 어떤 소수로도 나누어떨어지지 않는지"만 확인하면 된다.

그러면 계산시간을 줄일 수 있다.

 

public class Main {
    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) { //3부터 시작해서 홀수만 검사 (짝수는 소수가 아님)
            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++) {
            System.out.println(prime[i]); //모든 소수를 출력한다.
        }

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

이렇게 수정하면 나눗셈을 수행한 횟수가 78022에서 14622로 줄어든다.

그런데 여기서 좀 더 효율적으로 코드를 개선할 수 있는데

"정수 n의 제곱근 이하의 어떤 소수로도 나누어떨어지지않으면 n은 소수"라는 점을 생각하면 된다.

다시말해서, n의 제곱근 이하의 소수들만 가지고 판단해도 같은 결과를 낼 수 있는것이다.

public class Main {
    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++) { //n의 제곱근 이하의 소수들에 대해서만 검사
                counter+=2; //prime[i]*prime[i] 곱셈연산 + n%prime[i] 나눗셈연산 총 2번
                if(n%prime[i]==0){ //나누어떨어지면 소수가 아님
                    flag = true;
                    break;
                }
            }
            if(!flag){ //끝까지 나누어떨어지지 않으면 배열에 추가
                prime[ptr++] = n;
                counter++; //마지막까지 나누어떨어지지않으면 위의 for문안으로 안들어간다. 따라서 prime[i]*prime[i] 곱셈연산 1번 추가
            }
        }

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

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

그 부분을 고려하면 이렇게 더 효율적인 코드를 작성할 수가 있다.