소수(솟수) : 나머지가 0이 나오고 자기자신으로만 나누어지는 수
예) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, ...
예) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, ...
#include <stdio.h>
int nextprime(int prime)
{
int next, isprime, k;
{
int next, isprime, k;
isprime = 1;
if( isprime == 1)
return 2;
else if( isprime == 2)
return 3;
else {
// 주어진 솟수에 2씩 증가시키며 솟수인지 테스트
// 소수의 특성상 "2"를 제외한 끝자리는 항상 1, 3, 5, 7, 9 중에 하나이다.
for( next = prime+2; ; next += 2, isprime =1 ) {
// 예) 소수 "13"의 반 값인 7이상으로 제산 연산할 의미가 없다.
for( k = next/2; k >= 2; k--) {
if( next % k == 0 ) {
isprime = 0;
break;
}
} // for(k)
return 2;
else if( isprime == 2)
return 3;
else {
// 주어진 솟수에 2씩 증가시키며 솟수인지 테스트
// 소수의 특성상 "2"를 제외한 끝자리는 항상 1, 3, 5, 7, 9 중에 하나이다.
for( next = prime+2; ; next += 2, isprime =1 ) {
// 예) 소수 "13"의 반 값인 7이상으로 제산 연산할 의미가 없다.
for( k = next/2; k >= 2; k--) {
if( next % k == 0 ) {
isprime = 0;
break;
}
} // for(k)
if( isprime == 1)
return next;
return next;
} // for(next)
return 0;
} // else
}
}
'IT > 알고리즘' 카테고리의 다른 글
| 타 변수 없이 서로의 값을 치환하는 방법 (0) | 2008.07.16 |
|---|---|
| + integer 값을 - integer 값으로 바꾸는 가장 간단한 방법 (0) | 2008.07.16 |
| qsort (퀵 정렬) - 재귀, 비재귀, 삽입정렬, 난수발생 (1) | 2008.07.15 |
| 스트링에 대한 permutation을 구하는 알고리즘 (0) | 2008.07.15 |
| mmap (메모리맵) (0) | 2008.07.08 |
쩐의시대
나답게 살아가고 나답게 살아가자