소수 판별

소수 찾기

소수 (Prime number): 어떤 자연수 N에 대하여 1과 N으로 밖에 나누어 떨어지지 않는 수

 

 

1. 소수의 성질을 이용한 구현

bool isPrime (int N) {
  for (int i = 2; i*i < N; i++) {
    if (N % i == 0) return false;
  }
  
  return true;
}

N이 소수인지 판별하기 위해서는 N-1까지 모두 나눠볼 필요 없이 $ \sqrt(N) $ 까지만 나눠보면 된다.

 

왜 why?

$ N $이 만약 합성수라면 $ p*q $로 표현이 되기 때문에 두 수 중 한개는 항상 $ \sqrt(N) $ 이하, 다른 한 수는 항상 $ \sqrt(N) $ 이상이기에 $ i < N $ 까지 순회하지 않고, $ i \leq \sqrt(N) $까지 순회해도 괜찮다.

 

• 시간복잡도: $ O(\sqrt(N)) $

 

 

2. 에라토스테네스의 체

N이 작을 때, ($ N \leq 10,000,000 $) 2부터 N까지의 소수를 찾는 가장 효율적인 방법이다. 어떤 N이 소수이면 N의 배수는 모두 소수가 아니라고 체크한다. 이 과정을 반복하며 표를 만든다.

bool prime[10000000];

void sieve() {  
  for (int i = 2; i <= num; i++) {
    if (!prime[i]) {
      for (int j = i*2; j <= num; j+= i) 
        prime[j] = true;
    }
  }
}

• 시간 복잡도: $ O(\log \log N) $

 

최적화

#define maxN 7500000

bool prime[maxN];

void seive() {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;

	// 1. 2를 제외한 짝수는 모두 합성수이므로 짝수는 반복문에서 배제
    for (int i = 4; i < maxN; i+= 2)
        prime[i] = false;

	// 2. i의 값의 검사는 root(N)까지만
    for (int i = 2; i*i <= maxN; i++) {
        if (prime[i]) {
        
        	// 3. 중복 피해주기
            // 수가 너무 커지면 i가 너무 커지기 때문에 int j = 2*i로 웬만하면 쓰자.
            for (int j = i*i; j <= maxN; j += i) {
                prime[j] = false;
            }
        }
    }
}

 

 

 

아래 부터는 어떤 수가 소수인지 확률적으로 판단해주는 알고리즘이다.

정수론의 영역이고, 말그대로 확률이기 때문에 소수로 판별했어도 합성수일 가능성이 있다.

3. 페르마의 소정리를 이용한 소수 판별

4. 밀러-라빈 소수판별