质数问题:Primer类设计
给定一个整数N，返回不大于整数N的所有质数的集合
解决这个问题，其实古代有位印度数学家已经给出了行之有效的算法，有埃拉托斯特尼筛法(sieve of Eratosthenes )，简称埃氏筛，也称质数筛,这是一种简单且历史悠久的[筛法]，用来找出一定范围内所有的质数。所使用的原理是从2开始，将每个素数的各个倍数，标记成合数,一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。通常在是在n小于1000万左右时找到所有小于n的素数的最有效方法之一
以下是通过质数筛找到所有小于或等于给定整数n的素数的算法：
- Step1: 创建一个从2到N的连续整数列表：（2，3，4，…，n）。
- Step2:最初，让一个起始变量k等于2，第一个质数。
- Step3:从k2开始，以k的增量进行计数，并在列表中标记这些大于或等于k2本身的数字。 这些数字将是k(k + 1)，k(k + 2),k(k + 3),......等。
- Step4:在未标记的列表中查找大于k的第一个数字。如果没有这样的号码，停下来。否则，让k等于这个数（这是下一个素数），从第3步开始重复。
当算法终止时，列表中所有未标记的数字都是质数。让我们以N= 70时为例。因此我们需要打印所有小于或等于70的质数找出来。
根据该算法，我们将标记所有可被2整除且大于或等于2的数。
现在，我们移至下一个未标记的数字3，并标记所有3的倍数且大于或等于其平方的数字。
我们移到下一个未标记的数字5并标记5的所有倍数，并且大于或等于其平方。
我们移到下一个未标记的数字7并标记7的所有倍数，并且大于或等于其平方。
C++实现方案：
以下是上述算法的实现。 在以下实现中，大小为n的布尔数组arr []用于标记质数的倍数。
#ifndef __UTILS_PRIMER_HH__
#define __UTLS_PRIMER_HH__
#include <bits/stdc++.h>
#include <vector>
class Primer
{
private:
/* data */
public:
//判断传入参数是否素数
static bool isPrime(long n);
//查找给定整数n的下一个素数
static long nextPrime(long n);
//查找给定整数n的前一个素数
static long prevPrime(long n);
//返回一个指定整数区间的质数列表
static std::vector<long> primerList(long start, long last);
//返回给定整数n之前的质数列表
static std::vector<long> sieveOfEratosthenes(long n);
};
std::vector<long> Primer::sieveOfEratosthenes(long n)
{
/**
创建一个布尔数组“ prime [0..n]”，并将所有条目初始化为true。
如果i不是质数，则prime [i]的值最终将为false，否则为true。
*/
bool p[n + 1];
memset(p, true, sizeof(p));
for (auto k = 2; k * k < n; k++)
{
if (p[k] == true)
{
for (auto j = k * k; j <= n; j += k)
{
p[j] = false;
}
}
}
std::vector<long> res;
for (auto m = 2; m <= n; m++)
{
if (p[m])
[图片上传中...(ss8.png-d40d73-1586557079824-0)]
{
res.push_back(m);
}
}
return res;
}
#endif
那么“质数筛算法”的时间复杂度是多少呢？
为了分析它，我们取一个数n，任务是打印小于n的素数。因此，根据质数筛的定义，对于每个素数，它必须检查素数的倍数并将其标记为复合数。这个过程一直持续到最大质数p小于n为止。
如果假定将一个数字标记为复合数字所花费的时间是恒定的，则循环运行的次数等于：
剩下来就是用到高中的代数基础将这个表达式做一些等价变换，提取n的形式如下
根据素数的倒数之和，这个也是公元前3世纪，欧几里得已经证明，我们直接用这个结论就是
证明方法，可以查看上面链接的提供维基百科提供的证明过程，我们只需知道基于静态语言实现质数筛算法的时间复杂度就是
其中的N就是趋向无穷大的正整数，空间复杂度很一目了然嘛就是S(N)
Python实现方案
class Primer:
@staticmethod
def sieveOfEratosthenes(n):
p=[True for i in range(n+1)]
k=2
while(k*k<=n):
if(p[k]==True):
for i in range(k*k,n+1,k):p[i]=False
#end-if
k+=1
#end-while
res=[]
for k in range(2,n):
if p[k]:
res.append(k)
#end-for
return res
#end-def
#end-class
性能测试 Cython vs Python
这里其实一个扩展话题已经和本文的主题关系不大，下文的目地将要通过对比C++和Python对同一个算法实现的性能比较，其实不外乎告诫读者基于Python语言写的算法实现用于生产环境都是扯蛋的，理由非常充份"慢！慢！慢！"，这些都是热衷于鼓吹Python的狂热份子从来不会正视的问题，因为Python是解析语言，Python每条语句解析为机器语言过程中当中Python引擎已经经历一个漫长繁琐的过程变量类型检查以及内存分配,当然还有一个沉重的枷锁“全局解析器锁”。因此算法实现仅适合于静态语言，后来Cython,PyPy等第三方语言的出现拓宽了Python的前景，Cython的出现并没有取代Python之意，因为Cython的解析器仍然要基于Python解析器上下文环境协同运行的，只是使用了Cython关键字修饰的变量、函数由Cython解析器翻译成C/C++代码,进而编译成可执行模块，最终由Python引擎去调用该模块。
- Python的实现，运行代码如下
if __name__=='__main__': m=Primer() import timeit start=timeit.default_timer() res=m.sieveOfEratosthenes(17387523) end=timeit.default_timer() print(res) print("耗时:{}ms".format(end-start))
我们仅是粗略的测试，运行3次，取其中1次运行最快的如下图，即3.197621931998583s
注意:python的timeit默认的时间单位是秒/s
OK,上面我们用Cython做些特殊处理
待续.....
