[C언어] 에라토스테네스의 체 함수

#include <math.h> // sqrt 함수 사용을 위한 include
#define MAX_PRIME_NUMBER 100000 // 원하는 숫자로 변경 가능
 
unsigned int g_arrEratos[MAX_PRIME_NUMBER + 1] = {0, };
 
void fnEratos(unsigned int nLastElement)
{
    unsigned int nEratosLastElement = (int)sqrt(nLastElement) + 1;
    
    // 숫자 1 은 소수가 아님
    g_arrEratos[1] = 1;
    
    for(unsigned int i = 2; i <= nEratosLastElement; i++)
    {    
        unsigned int nSecondOperand = i;
        for(unsigned int nBuffer = i * 2; nBuffer <= nLastElement; nBuffer += nSecondOperand)
        {
            g_arrEratos[nBuffer] = 1;
        }
    }
}
 
// <사용법>
// 1. fnEratos(MAX_PRIME_NUMBER); 호출
// 2. NUMBER 가 소수인지 알고 싶다면 g_arrEratos[NUMBER] 을 판별하면 된다.
// 2.1. 0 이면 소수 O
// 2.2. 1 이면 소수 X