[Algorithm] 소수 구하기

2부터 N까지 소수 구하는 법

1. 2부터 N까지 하나 하나 나눠보며 구함

2. 3부터 N까지 홀수의 경우만 소수의 제곱근 보다 작은지 확인하면서 작은 경우 나눠보며 구함

3. 에라토스테네스의 체, 2, 3, 5, 7의 배수를 제외한 값을 구함 (N < 121인 경우, 7² < 100, 11² > 120이므로)

4. 3부터 N까지 홀수의 경우만 소수를 담은 배열(index0: 2)을 이용해 나누어 떨어지는지 확인 후 나누어지지 않으면 소수 배열에 담아 앞에서 한 것을 반복해서 구함

5. 5부터 N까지 홀수의 경우만 소수를 담은 배열(index0: 2, index1: 3)을 이용해 소수의 제곱근보다 큰지 확인하고 크지 않으면 해당 소수로 나머지 연산해보고 소수의 경우만 배열에 담음 이 것을 반복

2, 3, 5만 구현해보려 한다.

 

2. 3부터 N까지 홀수의 경우만 소수의 제곱근 보다 작은지 확인하면서 작은 경우 나눠보며 구함

class Primes2{
    public static void main(String[] args) {
        int [] primes = new int[500]; // 소수가 들어갈 배열
        int size = 1000; // 마지막 값
        primes[0] = 2;
        int index = 1; // primes의 위치 값

        for(int i = 3; i <= size; i+=2){ // 홀수만 연산
            boolean flag = false;
            for(int j = 3; j * j < i; j+=2){ // 홀수의 값만 제곱한 후 i보다 작은지 확인
                if(i%j==0) { // 소수가 아님
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                primes[index++] = i;
            }
        }

        for(int i = 0; i < index; i++) {
            if((i + 1) % 10 == 0) System.out.printf("%3d,\n", primes[i]);
            else if(i == index-1) System.out.printf("%3d\n", primes[i]);
            else System.out.printf("%3d, ", primes[i]);
        }
    }
}

 

3. 에라토스테네스의 체, 2, 3, 5, 7의 배수를 제외한 값을 구함 (N < 121인 경우, 7² < 100, 11² > 120이므로)

class prime3{
    public static void main(String[] args) {
        int [] primes = new int[500]; // 소수가 들어갈 배열
        int size = 1000;
        primes[0] = 2;
        int index = 1; // primes의 위치 값

        // 에라토스테네스의 체에 이용할 소수를 먼저 구함
        for(int i = 3; i * i <= size; i+=2){ // 홀수의 경우만 i*i가 1000보다 작은지 확인
            boolean flag = false;
            for(int j = 1; j < index; j++){ // 2를 제외한 소수가 들어있는 크기만큼만 반복
                if(i % primes[j] == 0){ // 소수배열에 들어있는 수로 나눠짐 소수 아님
                    flag = true;
                    break;
                }
            }
            if(!flag){
                primes[index++] = i;
            }
        }

        System.out.println("에라토스테네스의 체로 이용할 소수");
        for(int i = 0; i < index; i++) {
            if((i + 1) % 10 == 0) System.out.printf("%3d,\n", primes[i]);
            else if(i == index-1) System.out.printf("%3d\n", primes[i]);
            else System.out.printf("%3d, ", primes[i]);
        }

        int [] arr = new int[size-primes[index-1]];
        for(int i = primes[index-1] + 1; i <= size; i++){
            arr[i - primes[index-1] - 1] = i;
        }
        System.out.println("아직 소수를 구하지 못한 32부터 1000까지 배열에 담음");
        System.out.println(Arrays.toString(arr));

        int sieve = index; // 채로 이용될 소수의 마지막 위치값

        for(int i = 0; i < arr.length; i++){ // arr의 0번째부터 마지막까지 하나 씩 출력
            boolean flag = false;
            for(int j = 0; j < sieve; j++){ // primes에 들어있는 값 중 0부터 sieve까지 출력
                if(arr[i] % primes[j] == 0){ // 나눠지면 채로 거름
                    flag = true;
                    break;
                }
            }
            if(!flag) primes[index++] = arr[i];
        }

        for(int i = 0; i < index; i++) {
            if((i + 1) % 10 == 0) System.out.printf("%3d,\n", primes[i]);
            else if(i == index-1) System.out.printf("%3d\n", primes[i]);
            else System.out.printf("%3d, ", primes[i]);
        }
    }
}

 

5. 5부터 N까지 홀수의 경우만 소수를 담은 배열(index0: 2, index1: 3)을 이용해 소수의 제곱근보다 큰지 확인하고 크지 않으면 해당 소수로 나머지 연산해보고 소수의 경우만 배열에 담음 이 것을 반복

public class Primse5 {

    public static void main(String[] args) {
        int[] primes = new int[500]; // 소수가 들어갈 배열
        int index = 2;   // primes의 위치 값
        primes[0] = 2;
        primes[1] = 3;

        for(int n = 5; n <= 1000; n+=2){
            boolean flag = false;
            for(int i = 1; primes[i] * primes[i] <= n; i++){ // 제곱보다 n이 크거나 같은 경우
                if(n % primes[i] == 0){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                primes[index++] = n;
            }
        }

        for(int i = 0; i < index; i++) {
            if((i + 1) % 10 == 0) System.out.printf("%3d,\n", primes[i]);
            else if(i == index-1) System.out.printf("%3d\n", primes[i]);
            else System.out.printf("%3d, ", primes[i]);
        }
    }
}