소수 구하기

이 방법은 에라토스테네스가 고안한 방법으로, 여러 수를 체를

이용해 거르는 모양과 흡사하다고 해서 아리스토테네스의 체라고 불린다.

2부터 N까지의 수 중 소수를 구한다고 하자.

이 때 K가 소수일 때 K의 배수는 소수가 될 수 없다. 가장 작은 소수는 2이며,

따라서 2의 배수는 소수가 될 수 없다. 이 때 모든 2의 배수에 체크를 시켜둔다.

체크되지 않은 수 중 가장 작은 수는 3이고, 3의 배수에도 모두 체크한다.

이러한 방법으로 N까지 검사하면 2~N 사이에 있는

모든 소수를 빠른 시간 내에 구할 수 있다.

 

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

 

#define MAX 1000000

 

int main()

{

 int *ptr;

 int i,j;

 clock_t stime, etime;

 stime = clock();

 

ptr = (int*)malloc(sizeof(int)*MAX);
 if(ptr==NULL){
        printf("Error:memory allocation error!");
 }
 memset(ptr,0x00,sizeof(int)*MAX);

 

 for(i=2; i<MAX ;i++)

 {

  if(ptr[i]==1)

   continue;

  for(j=i+i ;j<MAX ;j+=i)

   ptr[j]=1;

 

 }

 

 for(i=2 ;i<MAX ;i++)

 {

  if(ptr[i]==0)

   printf("%d ",i);

 }

 

 etime=clock();

 printf("time: %.3fs\n",(double)(etime-stime)/CLOCKS_PER_SEC);

 return 0;

}

Result
100만 : 0.123s
1000만 : 1.569s
1억 : 20.290s

이 시간보다 빠른 구현을 해 보기~


sqrt() 이용은 추후에 다시