알고리즘/알고리즘 코드
[C언어] 에라토스테네스의 체 함수
ahdelron
2020. 4. 11. 20:40
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#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
|
cs |