소수 판별

 

 

---

소수(prime)란?

1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 뜻함 (이때 1은 소수가 아니다)

예) 2, 3, 5, 7, 11, 13 ...

 

소수 판별 방법

방법1. 숫자 N이 주어질 때, 2 ~ (N - 1) 까지 수 중 나누어 떨어지는 수가 없으면 소수이다

- 1과 자기자신을 제외한 나누어 떨어지는 수가 없어야 소수이므로 반복문을 통해 구하는 가장 간단한 방법

- 시간복잡도 : O(N) 

- 단 범위가 너무 클 경우 시간 초과 발생 가능

private static boolean isPrime(int n) {
    // 2 ~ n - 1 사이 수 중 나누어 떨어지는 수가 있으면 소수 아님
    for(int i = 2; i <= n - 1; i++) { 
        if(n % i == 0) return false;
    }

    return true;
}

 

 

방법2) 숫자 N이 주어질 때, 2 ~ N의 제곱근까지의 수 중 나누어 떨어지는 수가 없으면 소수이다.

- 시간 복잡도 : O(N^1/2)

 

약수의 성질

1) 모든 약수 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알수 있다.

2) 따라서 특정 자연 수의 모든 약수를 찾을 때 "가운데 약수(제곱근)"까지만 확인하면 연산 횟수를 줄일 수 있다

 

16의 약수는 아래와 같고 제곱근인 4 이후로는 대칭성 가지므로, 제곱근까지만 나누어 떨이지는지 확인하여 연산 횟수 줄임

1 2 4 8 16 

- 1 * 16
- 2 * 8
- 4 * 4
- 8 * 2
- 16 * 1

private static boolean isPrime(int n) {
    // 2 ~ n - 1 사이 수 중 나누어 떨어지는 수가 있으면 소수 아님
    for(int i = 2; i <= Math.sqrt(n); i++) { 
        if(n % i == 0) return false;
    }

    return true;
}

 

 

 

방법3) 에라토스테네스의 체 알고리즘 사용 

- 시간복잡도 O(Nlog(logN)) 

수학 잘하는 사람들 부럽다.. 문제 풀이 수학 다 잊어버림

절차
 1) 가장 먼저 소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다
 2) 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다 (이때 1은 소수가 아니므로 제외)
 3) 3의 배수를 지울 때 이미 지워진 숫자의 경우 건너뜀 --- 반복
 4) 2부터 남아있는 숫자 출력

 

 

*참고. 동빈나 강사님 유튜브

https://www.youtube.com/watch?v=5ypkoEgFdH8 

 

 

*백준 문제(1929번). 소수 구하기 

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

1929번: 소수 구하기

 

해당 문제의 경우 반례가 존재했다.

입력 1 2
출력 2

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static void process() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken()); // M이상
        int N = Integer.parseInt(st.nextToken()); // N이하

        int[] data = new int[N + 1];
        for(int i = 1; i <= N; i++) data[i] = i;

        for(int i = 2; i <= N; i++) {
            if(data[i] == 0) continue;

            for(int j = 2 * i; j <= N; j += i) {
                data[j] = 0;
            }
        }

        for(int i = M; i <= N; i++) {
            if(i == 1) continue;
            
            if(data[i] != 0) sb.append(i).append("\n");
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
        process();
    }
    
}

 

 

*백준 문제(2960). 에라토스테네스의 체

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

2960번: 에라토스테네스의 체

 

해당 문제의 경우 소수에 해당하는 숫자도 지우는게 특징이었다.

 

제출코드

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static void process() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] data = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            data[i] = i;
        }

        int cnt = 0;
        Loop1 :
        for(int i = 2; i <= N; i++) {
            if(data[i] == 0) continue;
            for(int j = i; j <= N; j += i) {
                if(data[j] == 0) continue;

                data[j] = 0;
                cnt += 1;

                if(cnt == K) {
                    sb.append(j);
                    break Loop1;
                }
            }
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
        process();
    }
    
}

 

 

*백준 문제(15965). K번째 소수

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

15965번: K번째 소수

 

- 에라토스테네스의 체를 사용해서 소수를 구하는 것은 동일

- 최대치에서 실수했는데 K 최대치 500,000일때 소수를 알고 배열 크기를 지정해야 한다. (7,368,791)

- 자료 유형에 따라 메모리와 시간이 차이 남을 확인 가능했음

아래 int (4byte), 위 boolean(1byte)

 

 

제출코드1. int형 풀이

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
     
    static int MAX = 7368791;

    static void process() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int K = Integer.parseInt(br.readLine());

        int[] data = new int[MAX + 1];
        for(int i = 2; i <= MAX; i++) {
            data[i] = i;
        }

        for(int i = 2; i <= MAX; i++) {
            if(data[i] == 0) continue;

            for(int j = i + i; j <= MAX; j += i) {
                data[j] = 0;
            }
        }

        int cnt = 0;
        for(int i = 2; i <= MAX; i++) {
            if(data[i] != 0 && ++cnt == K) {
                sb.append(i);
                break;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        process();
    }
    
}

 

제출코드2. boolean형 풀이

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
     
    static int MAX = 7368791;

    static void process() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int K = Integer.parseInt(br.readLine());

        boolean[] data = new boolean[MAX + 1];
        Arrays.fill(data, true);

        for(int i = 2; i <= MAX; i++) {
            if(!data[i]) continue;

            for(int j = i + i; j <= MAX; j += i) {
                data[j] = false;
            }
        }

        int cnt = 0;
        for(int i = 2; i <= MAX; i++) {
            if(data[i] && ++cnt == K) {
                sb.append(i);
                break;
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }


    public static void main(String[] args) throws Exception {
        process();
    }
    
}