[정수론] 소수 구하기

 

 

소수 구하기의 핵심이론

 

대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다.

 

에라토스테네스의 체란?

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수를 출력한다.

 

 

에라토스테네스의 체를 사용할 때 시간 복잡도는?

 

일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N²) 라고 판단 할 수 있다.

하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르지만, 일반적으로 O(Nlog(logN))이다.

그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

 

 

예제 1

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] A = new int[n+1];

        for (int i = 2; i <= n; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(A[i] == 0) {
                continue;
            }
            for (int j = i+i; j <= n; j = j+i) {
                A[j] = 0;
            }
        }
        for (int i = m; i<=n; i++) {
            if(A[i] != 0) {
                System.out.println(A[i]);
            }
        }
    }
}

 

 

 

 

예제 2

https://www.acmicpc.net/problem/1456

1456번: 거의 소수

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        long min = sc.nextLong();
        long max = sc.nextLong();
        long[] A = new long[10000001];

        for (int i = 2; i < A.length; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(A.length); i++) {
            if(A[i] == 0) {
                continue;
            }
            for (int j = i+i; j < A.length; j = j+i) {
                A[j] = 0;
            }
        }
        int count = 0;
        for (int i = 2; i < 10000001; i++) {
            if (A[i] != 0) {
                long temp = A[i];
                while((double)A[i] <= (double)max/(double) temp) {
                    if ((double)A[i] >= (double)min/(double) temp) {
                        count++;
                    }
                    temp = temp * A[i];
                }
            }
        }
        System.out.println(count);
    }
}

 

 

 

예제 3

 

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[10000001];

        for (int i = 2; i < A.length; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(A.length); i++) {
            if (A[i] == 0) {
                continue;
            }
            for (int j = i+i; j < A.length; j = j+i) {
                A[j] = 0;
            }
        }
        int i = n;
        while (true) {
            if (A[i] != 0) {
                int result = A[i];
                if(isPalindrome(result)) {
                    System.out.println(result);
                    break;
                }
            }
            i++;
        }
    }

    private static boolean isPalindrome(int result) {
        char temp[] = String.valueOf(result).toCharArray();
        int s = 0;
        int e = temp.length - 1;

        while (s < e) {
            if (temp[s] != temp[e]) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

 

 

 

 

 

예제 4

https://acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();

        boolean[] check = new boolean[(int) (max - min + 1)];

        //2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복하기
        for (long i = 2; i*i <= max; i++) {
            long pow = i*i;
            long start_index = min/pow;
            if (min % pow != 0) {
                start_index++; //나머지가 있으면 1을 더해야 min보다 큰 제곱수에서 시작됨.
            }
            for (long j = start_index; pow * j <= max; j++) {
                check[(int) ((j * pow) - min)] = true;
            }
        }
        int count = 0;
        for (int i = 0; i <= max - min; i++) {
            if(!check[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}