[C] 소수 구하기 / 에라토스테네스의 체 / 소수 구하기 최적화 / 1000개의 소수 구하기 / 범위 내의 소수 구하기

먼저 코드입니다. 선 코드 후 이해하도록 하겠습니다.

100이하의 소수찾기 (에라토스테네스의 체)

#include <stdio.h>

int main(int argc,char *argv[]) {

int number = 100;         // 100이하의 소수 찾기
int arr[101] = {0};		  // 2부터 100까지 들어갈 배열 만들어주기
  
  for(int i = 2; i <= number; i++) {
    arr[i] = i;           // 2~100까지 배열에 넣어주기
  }
  for(int i = 2; i * i <= number; i++) {
    if(arr[i] == 0) continue;
    for(int j = i * i; j <= number; j += i) {
      arr[j] = 0;
    }
}
  for(int i = 2; i <= number; i++) {
    if(arr[i] != 0) {
      printf("Prime Number : %d \n",arr[i]);
      } 
    }
  return 0;
  }

▲ 두 번째 for에서의 아이디어가 핵심입니다.

N개의 소수 구하기, 임의의 자연수 N에 대해 소수를 구하는 코드를 작성해보고자 합니다.

소수란 1과 자기 자신으로 나누어 떨어지는 1 이외의 수를 뜻합니다.

중,고등학교 때부터 봐온 소수는 현대사회에서 RSA 암호를 통한 전자서명에 활용되는 등

필수적인 역할을 수행하고 있습니다.

코드를 작성하기에 앞서 소수에 대해 고민한 것을 기술해보고자 합니다.

1) 짝수는 소수가 될 수 없다.

소수의 정의를 생각해보면 금방 알 수 있는데요.

소수란 1과 자기 자신으로 나누어 떨어지는 1 이외의 수라고 했기 때문에, 짝수는 절대 소수가 될 수 없습니다.

2) 범위가 주어졌을 때, 각 수를 판별 시 그 수의 제곱근까지만 판별해도 소수 판별이 가능하다.

이게 도대체 무슨 말인가 싶을텐데, 어떠한 자연수 n이 서로 다른 p*q로 표현될 때

p <= √n, q >= √n으로 나타납니다.

따라서 n보다 작은 모든 소수를 찾고 싶을 때, 2부터 n까지가 아닌 2부터 √n까지로 범위를 줄일 수 있습니다.

+α) 모든 소수는 6k±1로 정리가 된다.

이 역시 자명합니다.

6k+1

6k+2

6k+3

6k+4

6k+5

6k부터 6k+5까지 나열해봅시다.

6k-1

6k+1

6k+2

6k+3

6k+4

2x3xk 2(3k+1) 3(2k+1) 2(3k+2)

이와 같이 증명됩니다. 직접 수를 넣어봐도 맞습니다.

하지만 6k±1로 표현되는 수가 있다고 해서 모두 소수인 것은 아닙니다!!!

-2와 α는 티스토리(https://loosie.tistory.com/267)를 참고했습니다.

범위가 주어졌을 때, 소수를 가장 빠르게 판별할 수 있는 방법은 에라토스테네스의 체입니다.

현대에 들어와서도 에라토스테네스의 체보다 빠른 방법은 없다고 하네요. (단, 범위가 주어졌을 때입니다.)

에라토스테네스의 체는 위에서 기술한 2번 내용의 아이디어를 사용합니다.

가장 일반적인 경우로 범위가 100까지의 수라고 가정했을 때, 2부터 √100까지의 범위내에서 소수를 모두 구합니다.

그런 다음, 그 소수들의 배수를 모두 지워주시면 남는 수들이 모두 소수가 됩니다.

출처 : 위키백과 - 에라토스테네스의 체(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)

코드는 위에 올려놓은대로인데요.

위 코드에서

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

만 다뤄보도록 하겠습니다.

2~100까지 판별을 해볼건데, 굳이 그 수가 아니라 그 수의 제곱이 주어진 수보다 작으면 됩니다.

위에서 기술한 2의 내용이 여기서 적용 됩니다.

아래 반복문은 소수의 배수들을 절삭해주는 역할을 하는데, 초기식이 i의 제곱인 것이 눈에 뜁니다.

i의 제곱으로 초기식을 구성하여도 문제가 없는 이유는 그 전까지의 i*i의 배수는 어차피 절삭되기 때문입니다.

티스토리툴바