[알고리즘] 소수(prime number) 구하기 _에레스토테네스의 체

소수 구하기 에라스토테네스의 체

소수(priime_number)란?

어떤수의 약수가 1과 자기자신만 가지는 수

ex)  2, 3, 5, 7, 11, 13, 17, ...

소수가 아닌 수의 특징은 자기자신과 1이 아닌 다른수로 나누어 떨어질 수 있다.

즉 1과 자기자신이 아닌 다른수의 곱으로 나타낼수 있다.

ex) 17 ( 소수 ) : 1 * 17

ex) 12( 소수아님)  : 1 * 12, 2 * 6, 3 * 4, 4 * 3, 6 * 12, 12 * 1

 

 

에라스토테네스의 체

100개의 배열을만들고 모두 0으로 초기화

0번째방, 1번째 은 제외하고 2번째 방부터 값이 0이면 소수로 판단 출력한다.

출력후 그 해당하는 값의 배수를 모두 1로 바꾼다.

 

반복...

 

루프의 속도를 개선해보자.

2를 제외한 짝수는 절대 소수가 아니다.   -> 3부터 2씩 증가한다.

이미 이전에 제외된 수는 참고 하지 않는다. -> 자기자기의 제곱부터 2씩 증가하는 값을 1로 바꾸어 나간다.

#include <stdio.h>  //에라스토테네스의 체  
  
int arr[100];  

int main()  
{  
    int cnt = 1;  

    int i, j;  

    printf("2\n");  

    for ( i =3 ; i < 100 ; i+=2)  
    {  
        if(arr[i]==0)  
        {  
            cnt++;  

            for(j=i; j<=100/i; j+=2)  

            {  
                arr[j*i] = 1;  
            }  
        }  
    }  
    printf("num : %d\n", cnt);  
}​