여기에서 N까지 모든 대체 소수를 인쇄하는 방법을 볼 것입니다. 대체 소수는 아래와 같습니다. N =15라고 가정합니다. 따라서 N까지의 소수는 {2, 3, 5, 7, 11, 13}입니다. 대체 소수는 {2, 5, 11}입니다. 이 문제를 해결할 수 있는 방법을 살펴보겠습니다.
알고리즘
printAlternatePrime(N)
Begin define one Boolean array prime of size N + 1, and fill with 1. for p := 2, p^2 is less than N, increase p by 1, do if prime[p] is true, then for all multiples of p, make the position 0 in prime array end if done set the flag for p := 2 to n, do if prime[p] is true, then if flag is set, then print p, and reset the flag else set the flag end if end if done End
예시
#include<iostream> using namespace std; void printAlternatePrime(int n) { bool prime[n + 1]; for(int i = 0; i<=n; i++) { prime[i] = true; } for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * 2; i <= n; i += p) //all multiples will be false prime[i] = false; } } bool prime_flag = true; for (int p = 2; p <= n; p++) { if (prime[p]) { if (prime_flag) { cout << p << " "; prime_flag = false; } else { prime_flag = true; //set to print next prime } } } } main() { int n; cout << "Enter upper limit: "; cin >> n; cout << "Alternate prime numbers are: "; printAlternatePrime(n); }
출력
Enter upper limit: 20 Alternate prime numbers are: 2 5 11 17