使用 Sundaram 筛法在给定范围内生成素数的 C++ 程序
c++server side programmingprogramming
这是实现 Sundaram 筛法在给定范围内生成素数的 C++ 程序。该算法由 Sundaram 于 1934 年发现。
算法
开始
printPrimes(n)
在这里我们找出小于 n 的素数
我们将 n-2 减半。我们称之为 New。
New = (n-2)/2;
创建一个数组 marked[n]，用于将形式为 i+j+2ij 的数字与
其他数字分开，其中 1 <= i <= j
将 marked[] 的所有条目初始化为 false。
将所有形式为 i + j + 2ij 的数字标记为 true
其中 1 <= i <= j
对于 i=1 到 New
a) j = i;
b) 循环 While (i + j + 2*i*j) 2，然后打印 2 作为第一个素数。
其余素数的形式为 2i + 1，其中 i 是
未标记数字的索引。因此，对于所有 i
打印 2i + 1，使得 marked[i] 为假。
结束
示例代码
#include <bits/stdc++.h>
using namespace std;
int SieveOfSundaram(int m) {
int N= (m-2)/2;
bool marked[N + 1];
memset(marked, false, sizeof(marked));
for (int i=1; i<=N; i++)
for (int j=i; (i + j + 2*i*j) <= N; j++)
marked[i + j + 2*i*j] = true;
if (m > 2)
cout << 2 << " ";
for (int i=1; i<=N; i++)
if (marked[i] == false)
cout << 2*i + 1 << " ";
}
int main(void) {
int m = 10;
SieveOfSundaram(m);
return 0;
}
输出
2 3 5 7
