소수를 구하는데 고대의 그리스 수학자 에라스토스테네스에 의하여 개발된 에라스토스테네스의 체(Sieve of Erastosthenes)라는 알고리즘이 있다. 이 알고리즘은 정해진 범위 안의 소수를 찾아주는 비교적 간단한 방법이다. 이 알고리즘은 정해진 범위만큼의 배열을 생성한다. 만약 sieve[i]의 값이 0이면 i는 소수라는 의미이고 sieve[i]가 1이면 소수가 아니다. 처음에는 모든 배열의 값이 0으로 초기화된다. 즉 처음에는 모든 정수가 소수라고 가정한다. 알고리즘은 가장 작은 소수인 i=2부터 시작한다. 상식적으로 2의 배수는 소수가 아닌 것이 확실하다. 정해진 범위 안에서 2의 배수를 모두 찾아서 sieve[] 값을 1로 만든다. 즉 2, 4, 6, 8, ... 등의 인덱스를 갖는 원소들은 모두 1로 설정된다. 다음에 i를 3으로 하나 증가시킨다. 다시 3의 배수(3, 6, 9, ...)를 찾아서 sieve[i]를 1로 만든다. i를 다시 하나 증가시키면 sieve[4]는 이미 1이므로 다음 i 값으로 넘어간다. sieve[i]가 0인 다음 i를 찾아서 i의 배수를 모두 1로 만든다. 정해진 범위에 대하여 이와 같은 절차를 완료한 후에도 0값을 가지는 원소는 소수가 된다. 이 알고리즘을 이용하여 2부터 100사이의 소수를 찾아보라.
SIZE 상수의 값을 변환시키면 더 큰 범위까지의 소수를 구할 수 있다.
문제에서의 sieve[]가 a[]이다. i는 나누는 수, j는 나눠지는 수, k는 소수 아닌 것들을 거를 때 곱해주는 수이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> #define SIZE 100 int main(void) { int a[SIZE+1]={0}; int i,j,k; a[0]=1;a[1]=1; for(i=2;i<SIZE+1;i++) {if(a[i]==1) continue; for(j=2;j<SIZE+1;j++) {if(j%i==0) {for(k=2;j*k<SIZE+1;k++) a[j*k]=1;}}} for(i=0;i<SIZE+1;i++) if(a[i]==0) printf("%d ", i); printf("\n"); return 0; } | cs |
'컴퓨터 & 프로그래밍 & 전자공학 > C언어' 카테고리의 다른 글
| 정수의 합과 차 (0) | 2016.08.15 |
|---|---|
| 바이트 순서 알아보기 (0) | 2016.08.14 |
| 술에 취한 딱정벌레 (2) | 2016.08.13 |
| 2진수 변환기 (0) | 2016.08.12 |
| 2차원 행렬 (0) | 2016.08.12 |
