배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘

1. 알고리즘 개선 없는 1000 이하의 소수 찾기

package myTest1;
 
public class PrimeNumber1 {
 
    public static void main(String[] args) {
        int counter = 0;
        // 1000 이하의 소수를 열거함.
        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);
    }
    
}

결과

2. 배열을 사용해 3이상의 소수를 이중 for문으로 2씩 증가시켜 1000 이하의 소수 찾기

package myTest1;
 
public class PrimeNumber2 {
 
    public static void main(String[] args) {
        int counter = 0;    // 나눗셈의 횟수
        int ptr = 0;            // 찾은 소수의 개수
        int[] prime = new int[500];        // 소수를 저장하는 배열
        
        prime[ptr++] = 2;    // 2는 소수임
        // prime[0] = 2
        // prime[1] = null
        for(int n=3; n<=1000; n+=2){    // 대상은 홀수만 3,5,7,9,
            int i;
            // i=1; i<1 false
            // prime[1] = 3
            // n= 5 i=1 i<2 counter = 1; 5 % prime[1] 
            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);
    }
}

결과

3. 배열을 사용해 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다. 라는 소수 판단 조건을 가지고

1000 이하의 소수 찾기

package myTest1;
 
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++){
            System.out.println(prime[i]);
        }
        System.out.println("곱셈과 나눗셈을 수행한 횟수: " + counter);
    }
}

3개의 실행결과

나눗셈을 수행한 횟수는 78022, 14622, 3774 번이다.

알고리즘 개선을 통해 수행한 횟수를 줄일수 있었다.

소스 코드 첨부

myTest1.zip