在C ++中，备用素数直到N？
在这里，我们将看到如何打印所有备用质数直到N。备用质数如下所示。假设N=15。因此，直到N的素数为{2，3，5，7，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