소수 판별 3가지 방법 | 에라토스테네스의 체 | 자바 | Java

소수 판별 방법이 3가지나 있다는걸 몰랐다는 것에 반성하며,, 

나동빈님 블로그 및 유튜브 영상을 통해 본 내용 + 제 생각을 넣어 적어보겠음당

 

https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221233595886&redirect=Dlog&widgetTypeCall=true&directAccess=false

22. 에라토스테네스의 체

 

'에라토스테네스의 체'는 알고리즘 대회에도 많이 나온다고 하니.. 꼭 알아야한다고 합니닷~

 

소수판별 알고리즘은 다음과 같이 3가지가 있습니다.

 

아래에 나오는 모든 코드들은 백준 1929번을 풀며 짰던 코드들입니다!!

1. 모든 경우에서 약수가 있는지 여부를 체크

대부분의 코딩을 해본 사람들이라면 아는 직관적인 방법,,ㅎ

여기서 i/2를 한 이유는 어차피 절반 넘어가면 약수가 나올 수 없기 때문에! (2의 배수를 넘어가면 1의 배수만 남으니까!)

 

아래 코드는 백준 1929번  처음에 제출했던 시간초과 코드^^

M부터 N까지 중 소수 판별하는 문제입니닷

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        boolean prime = true;

        for(int i=M; i<=N; i++){
            for(int j=2; j<=i/2;j++){
                if(i % j == 0){
                    prime = false;
                    break;
                }
            }
            if(prime)
                sb.append(i+"\n");
            prime = true;
        }
        System.out.println(sb);
    }
}

 

2. 제곱근까지만 약수가 있는지 여부를 체크

제가 앞에서 i/2보다 좀 더 정확한 방법인 것 같네요!

왜냐면 제곱근을 기준으로 약수들이 대칭이거든여!

1 2 4 8 16 < 이걸 보시면 16의 제곱근 4를 기준으로 앞에서 약수가 나온 개수만큼 뒤에 반드시 나옵니닷!

다시 생각하면 제곱근을 포함해서 앞에까지 약수가 안나왔다면 뒤에도 안나온다는 겁니다!! (진짜 천재들,,,)

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        boolean prime = false;

        for(int i=M; i<=N; i++){
            for(int j=2; j<=(int)Math.sqrt(i);j++){
                if(i % j == 0){
                    prime = false;
                    break;
                }
                prime = true;
            }
            if(prime)
                sb.append(i+"\n");
            prime = true;
        }
        System.out.println(sb);
    }
}

 

3. 에라토스테네스의 체 : 대량의 소수를 한꺼번에 판별할 때 유리

예를 들어 1000이하의 소수를 알고 싶다면!

 

1) 1001의 크기를 갖는 배열 선언 (숫자 1의 인덱스를 1로 만들어주려고! 즉 1000의 인덱스를 1000으로 만드려고!)

 

2) 그 후엔 2부터 1000까지 차례로 자신을 제외한 자신의 배수를 지우면 됩니당! 

이미 지워졌다면 패쓰~ (이게 핵심인게! 4의 배수는 2의 배수와 겹치기 때문에 배제해줌!)

 

3) 그 후 2부터 시작해서(소수는 2가 최소임!) 지워지지 않은 숫자가 1000이하의 소수에요!

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int [] isPrime = new int[N+1];

        for(int i=2;i<=N;i++){
            isPrime[i] = i;
        }

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

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

        System.out.println(sb);
    }
}

 

근데 여기서 3번과 2번의 방법을 섞을 수도 있음 ㅋ

아래 코드를 보면 Math.sqrt가 있어여! 배수 거르기 할 때도 똑같이 제곱근 이하에서만 거르면 되니까~ 

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int [] isPrime = new int[N+1];

        for(int i=2;i<=N;i++){
            isPrime[i] = i;
        }

        for(int i=2;i<=(int)Math.sqrt(N);i++){
            if(isPrime[i] == 0) continue;
            for(int j=2*i;j<=N;j+=i){
                isPrime[j] = 0;
            }
        }

        for(int i=M;i<=N;i++){
            if(isPrime[i] != 0){
                sb.append(isPrime[i]+"\n");
            }
        }
        System.out.println(sb);
    }
}

 

생각보단 어렵지 않은 알고리즘이지만 몰랐다면 삽질을 한참 할 뻔 했다,,ㅎㅎ