C ++程序使用Sundaram筛子在给定范围之间生成素数

这是C ++程序，用于实现Sundaram筛，以在给定范围之间生成素数。该算法由Sundaram于1934年发现。

算法

Begin    printPrimes(n)    Here we find out primes    smaller than n, we reduce n-2 to half. We call it New.    New = (n-2)/2;    Create an array marked[n] that is going    to be used to separate numbers of the form i+j+2ij from    others where 1 <= i <= j    Initialize all entries of marked[] as false.    Mark all numbers of the form i + j + 2ij as true    where 1 <= i <= j    for i=1 to New       a) j = i;       b) Loop While (i + j + 2*i*j) 2, then print 2 as first prime.       Remaining primes are of the form 2i + 1 where i is       index of NOT marked numbers. So print 2i + 1 for all i       such that marked[i] is false. End

范例程式码

#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