[수학1]소수

Prime Number

• 소수 : 약수가 1과 자기 자신 밖에 없는 수
• N 이 소수가 되려면, 2보다 크거나 같고 , N-1 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• 1 부터 100 까지 소수
  • 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

 

소수와 관련된 알고리즘은 두가지가 있다.

1. 어떤 수 N 이 소수인지 아닌지 판별하는 방법

2. N 보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법(N 이하의 소수를 찾아내는 방법)

방법 1.소수의 정의를 이용한 풀이_시간복잡도 O(N)

public static boolean isPrime(int a){
    if (a == 1){
        return false;
    }
   for (int i=2; i < a; i++) {
       if (a % i == 0) {
            return false;
       }
   }
   return true;
}

방법 2.시간복잡도 O(N/2)

어떤 수가 소수가 아니라면 N = a x b 일 경우 (a<= b) a 의 최솟값은 2 이고 b 의 최댓값은 N/2 이다.

 

public static boolean isPrime(int a){
    if (a == 1){
        return false;
    }
   for (int i=2; i < a/2; i++) {
       if (a % i == 0) {
            return false;
       }
   }
   return

방법 3.시간복잡도 O(루트 N )

N = a x b (a <= b)

만약 N 이 소수가 아니라면 a 가 b 보다 작은 경우 항상 a 는 루트 N 보다 작고 b 는 루트 N 보다 크다.

왜냐하면 둘다 루트 N 보다 작은 경우 a < 루트 N , b <루트 N  인 경우 두 수는 axb < N 이므로 N 과 같지 않으므로 

성립될 수 없다. 두 수가 루트 N 보다 큰 경우 axb > N 보다 크므로 N 과 같지 않으므로 성립 될수 없다. 그래서 항상 N 이 소수가 아니라면 a < 루트 N , b > 루트 N  이므로 한 쪽에서 약수가 없어야 한다.

ex ) 24

      루트 24 = 4.xx 

      1 2 3 4 6 8 12 24 

      4를 기준으로 짝을 이루기 때문에 한쪽 부분에 대해서만 검사를 해도 그 수가 소수인지 아닌지 판별 가능하다

 

 

i <= 루트 N 

실수는 근사값이므로 사용하지않는것을 추천하다.

그래서 i * i <= n 를 사용하면 i <= 루트 N 표현을 정수만으로 표현할 수 있다. 

public static boolean isPrime(int a){
    if (a == 1){
        return false;
    }
   for (int i=2; i*i<=n; i++) {
       if (a % i == 0) {
            return false;
       }
   }
   return true;
}

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

방법 4.에라토스테네스의 체

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, {\displaystyle 11^{2}>120}

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

public static boolean[] Eratos(int n){
    boolean[] isCompositon = new boolean[n+1];
    isCompositon[0] =isCompositon[1] = true;
    for(int i=2; i< isCompositon.length; i++){
        if (isCompositon[i]) {
            continue;
        }
        isCompositon[i] = false;
        for (int j=2; i*j< isCompositon.length; j++) {
            isCompositon[i*j] = true;
        }
    }
   return isCompositon;
}

i * i 를 이용하는 이유

어떤 수의 제곱보다 큰 수는 이미 다 지워져 있다.

ex ) 11의 배수를 지울 경우  11 *2 (2의 배수에서 지움) 11 *3(3의 배수에서 지움) 11 *4(4의 배수에서 지움) ~ 11 *10(10의 배수에서 지움)

 

public static boolean[] Eratos(int n){
    boolean[] isCompositon = new boolean[n+1];
    isCompositon[0] =isCompositon[1] = true;
    for(int i=2; i< isCompositon.length; i++){
        if (isCompositon[i]) {
            continue;
        }
        isCompositon[i] = false;
        for (int j=i*i; j< isCompositon.length; j+=i) {
            isCompositon[j] = true;
        }
    }
   return isCompositon;
}

( i* 2 ~ i* (i-1))은 지워져 있으므로 i*i  부터 에라토스체를 걸러준다.

stack overflow 가 발생 할 수 있기 때뭉에 여기서 i*i 보다는 i*2 또는 i+2 로 표현한다.

ex) 100만 제곱일 경우 int 에 담으면 stack overflow 발생 

 

public static boolean[] Eratos(int n){
    boolean[] isCompositon = new boolean[n+1];
    isCompositon[0] =isCompositon[1] = true;
    for(int i=2; i< isCompositon.length; i++){
        if (isCompositon[i]) {
            continue;
        }
        isCompositon[i] = false;
        for (int j=i*2; j< isCompositon.length; j+=i) {
            isCompositon[j] = true;
        }
    }
   return isCompositon;
}

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