ที่นี่เราจะดูวิธีพิมพ์เลขเฉพาะสลับ (alternate prime numbers) จนถึง 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
}
}
}
}
int 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
