C++ 程序使用 Sundaram 筛法生成特定范围内的质数

本 C++ 程序实现 Sundaram 筛法，生成特定范围内的质数。该算法是 1934 年 Sundaram 发现的。

算法

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

更新于： 30-Jul-2019

415 次浏览

开启你的 职业生涯

完成课程获得认证

立即开始
广告