에라토스테네스의 체: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
잔글 코드 정리 |
||
18번째 줄:
=== 에라토스테네스의 체를 프로그래밍 언어로 구현 ===
◆ [[C++]]로 이 알고리즘을 다음과 같이 구현할 수 있다.
<source lang="cpp" start="0">
void Eratos(int n)
{
▲ // 만일 n이 1보다 작거나 같으면 함수 종료
▲ if(n<=1) return;
▲ /* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당
배열 참조 번호와 소수와 일치하도록 배열의 크기는
n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음) */
bool* PrimeArray = new bool[n + 1];
for (int i = 2; i <= n; i++)
PrimeArray[i] = true; /* 에라토스테네스의 체에 맞게 소수를 구함
만일, PrimeArray[i]가 true이면 i 이후의 i 배수는 약수로 i를
PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
소수가 아니게 된다. 그러므로 검사할 필요도 없다. */
for (int i = 2;
{
if (PrimeArray[i])
for (int j = i * i; j <= n; j += i)
}
// 이후의 작업 ...
}
</source>
| |||