用C++实现的增强Euler筛法程序
运行示例
PS H:\Read\num\x64\Release> .\eulerSievePro
EulerSievePro: a method to find out all primes below the number that you specify here please: 1234567890
Only the sum of all primes needed [y/n](y as default):
Start to work out the sum of all primes below 1234567890...
62106578 primes found in 8687 milliseconds.
PS H:\Read\num\x64\Release> .\eulerSievePro
EulerSievePro: a method to find out all primes below the number that you specify here please: 123456789
Only the sum of all primes needed [y/n](y as default):
Start to work out the sum of all primes below 123456789...
7027260 primes found in 828 milliseconds.
PS H:\Read\num\x64\Release> .\eulerSievePro
EulerSievePro: a method to find out all primes below the number that you specify here please: 12345678
Only the sum of all primes needed [y/n](y as default):
Start to work out the sum of all primes below 12345678...
809227 primes found in 94 milliseconds.
PS H:\Read\num\x64\Release>
对比用C++实现的Euler筛法程序里的eulerSieve和用C++实现的增强Eratosthenes筛法程序里的eSievePro，eulerSieve的性能优于eulerSieve；而eulerSievePro与eSievePro相比则互有优劣，在千万这个数量级eSievePro优于eulerSievePro，在亿级和十亿级eulerSievePro则要优于eSievePro。
增强Euler筛法的C++程序实现
为说明方便，把用C++实现的Euler筛法程序里的实现称为eulerSieve，而把这里的新实现称为eulerSievePro。
宏定义和全局量定义
1 typedef unsigned char u8;
2 //typedef uint64_t ulong;
3 typedef unsigned long ulong;
4 static std::vector<ulong> s_vecPrime;
main函数实现
1 int main()
2 {
3 printf(" EulerSievePro: a method to find out all primes below the number that you specify here please: ");
4 std::string strInput;
5 getline(std::cin, strInput);
6 ulong raw_last = 0;
7 if (!str2num(strInput, raw_last))
8 return 0;
9 printf("\n Only the sum of all primes needed [y/n](y as default): ");
10 getline(std::cin, strInput);
11 bool bDetail = (strInput == "n");
12 if (bDetail)
13 std::cout << std::endl << " Start to work out all primes below " << raw_last << "...\n";
14 else
15 std::cout << std::endl << " Start to work out the sum of all primes below " << raw_last << "...\n";
16 if (!eulerSievePro(raw_last))
17 return 0;
18 if (bDetail)
19 showDetails();
20 return 0;
21 }
eulerSievePro函数实现
1 bool eulerSievePro(ulong raw_last)
2 {
3 DWORD tickBegin = GetTickCount();
4 ulong last = raw_last / 2;
5 u8* pOdd = new u8[last];
6 if (!pOdd) {
7 printf("Lack of memory.\n");
8 return false;
9 }
10
11 ulong sum = 1;
12 ulong uplimit = 0;
13 s_vecPrime.push_back(2);
14 memset(pOdd, 1, last);
15 for (ulong halfIdx = 1; halfIdx < last; ++halfIdx) {
16 ulong num = (halfIdx + halfIdx) + 1;
17 if (pOdd[halfIdx] == 1) {
18 ++sum;
19 s_vecPrime.push_back(num);
20 }
21 for (ulong idx = 1; idx < sum; ++idx) {
22 if (uplimit != 0 && idx >= uplimit)
23 break;
24 ulong prime = s_vecPrime[idx];
25 ulong multiple = num * prime;
26 if (multiple >= raw_last) {
27 uplimit = idx;
28 break;
29 }
30 pOdd[multiple / 2] = 0;
31 if (num % prime == 0)
32 break;
33 }
34 }
35 std::cout <<" " << sum << " primes found in " << GetTickCount() - tickBegin << " milliseconds.\n\n";
36 delete []pOdd;
37 return true;
38 }
和用C++实现的Euler筛法程序里的eulerSieve函数实现相比，这里的eulerSievePro函数做了以下几方面的优化：
1、pOdd的动态申请的空间是s_pAll的一半，既节省了存储空间，又节省了全体偶数的筛去过程；
2、外层循环里，halfIdx的步长为1，对应的num变量的步长则为2，因为只需要用奇数去筛就可以；
3、引入了uplimit变量，动态控制乘法运算的分量上界，可以大为减少乘法运算的总次数。
增强Euler筛法示例说明
以筛出100以内（不含100）的所有素数为例来具体说明一下本程序实现的增强Euler筛法。
构建一个下标k（即代码里的halfIdx）由0到[100/2]-1的数组，下标k对应的数组单元记录奇数2k+1是否为素数，一开始数组全体单元的值都为1，即所有奇数都标记为素数。并构建一个素数动态队列，把2加入其中。
从数组下标1（对应奇数3）开始遍历数组单元，3被记录为素数，于是把3加入素数队列，接着开始用3筛选合数，素数队列里打头的2不参与合数筛选，这时会筛去3*3（即9），程序里的具体实现是把奇数9在数组中对应单元（下标为[9/2]=4）的值置为0，以表达9不是素数。
数组下标2对应单元的值为1，把对应的奇数5加进素数队列，随后筛去5*3（即15）和5*5（即25）。
数组下标3对应单元的值为1，把对应奇数7加进素数队列，随后依次筛掉7*3（即21）、7*5（即35）和7*7（即49）。
遍历到数组下标4时，其对应单元的值为0，对应的奇数9不会加入素数队列，这时会筛掉9*3（即27），但因为判断出9是3的倍数，随后就不会用9进一步去筛掉9*5（即45）。
数组下标5对应单元的值为1，把对应奇数11加进素数队列，随后依次筛去11*3（即33）、11*5（即55）和11*7（即77）。11*11（即121）因大于100而不做处理，此时把uplimit置为11。
数组下标6对应单元的值为1，把对应的奇数13加进素数队列，随后依次筛去13*3（即39）、13*5（即65）、13*7（即91）。13*11这一次乘法运算不会实施，因为当前内部遍历到的素因数11和uplimit值相等（内部的机制是此前11*11已经大于100，此次的13*11必然也大于100）。
数组下标7对应单元的值为0，对应的奇数15不会加进素数队列，这时会筛去15*3（即45），因为15是3的倍数，随后不会继续筛去15*5。
数组下标8对应单元的值为1，把对应的奇数17加进素数队列，随后依次筛去17*3（即51）和17*5（即85）。17*7（即119）因为大于100而不做处理，此时uplimit的值调整为7。
数组下标为9对应单元的值为1，把对应的奇数19加进素数队列，随后依次筛去19*3（即57）和19*5（即95）。因为uplimit为7，不需要再去计算19*7并判断其结果是否大于100。
数组下标为10对应单元的值为0，对应的奇数21为合数，随后会筛去21*3（即63）。
之后23进素数队列，依次筛去23*3和23*5。
25能筛去25*3，25*5大于100，uplimit调整为5。
27能筛去27*3。
29进素数队列，并筛去29*3。
31进素数队列，并筛去31*3。
33能筛去33*3（即99）。
35，因为35*3大于100，不能筛去任何数，此时uplimit调整为3。至此，筛查范围内的所有合数都已被筛除，剩下的遍历只是把剩余的素数加到素数队列。
辅助函数str2num和showDetails
showDetails的实现和用C++实现的Euler筛法程序里完全一样。
1 bool str2num(const std::string& str, ulong& val)
2 {
3 if (8 == sizeof(ulong)) {
4 if (str > "8589934592") {
5 printf("\n Invalid input - the biggest number could be 2^33.\n");
6 return false;
7 }
8 }
9 else {
10 if (str >= "4294967296") {
11 printf("\n Invalid input - the biggest number could be 2^32 - 1.\n");
12 return false;
13 }
14 }
15 size_t len = str.length();
16 val = 0;
17 for (size_t idx = 0; idx < len; ++idx) {
18 char ch = str[idx];
19 if (ch > '9' || ch < '0') {
20 printf("\n Invalid input - with non-numeric character.\n");
21 return false;
22 }
23 val = val * 10 + (ch - '0');
24 }
25 if (val <= 2) {
26 printf("\n Invalid input - at least 3.\n");
27 return false;
28 }
29 return true;
30 }
str2num函数用于把交互输入的字符串转化为整数。为支持更大范围的素数筛选，程序提供了ulong类型的备用定义：
typedef uint64_t ulong
不过输入一个很大的数，现有的筛选实现内存开销会很大。
另外，经测试发现，输入同样一个32位内的大数（小于2的32次方），eulerSievePro实现程序中把ulong定义为32位无符号整数比把ulong定义为64位无符号整数在处理性能上占显著优势。这应该和CPU的乘法运算实现有关，导致两个64位无符号数相乘会比两个32位无符号数相乘慢。
其他
https://github.com/readalps/EulerSievePro上放了eulerSievePro实现的源码文件，以及两个运行结果文件。
最新文章
- linux grep命令
- ThinkCmfX模板常量
- hdr_beg(host) hdr_reg(host) hdr_dom(host)
- iframe与include的区别
- Java多线程初学者指南（6）：慎重使用volatile关键字
- location.href的用户总结
- Android Studio使用技巧
- EasyUEFI
- Windows Mobile 6 sdk installation error, COM3 in use,please check the implementation
- [MFC美化] USkin使用详解-使用方法
- 在Pypi上发布自己的Python包
- wireshark抓包图解 TCP三次握手/四次挥手详解[转]
- Mysql 数据库常用配置命令
- 2019年华南理工校赛（春季赛）--L--剪刀石头布（签到）
- (整理)在REHL6.5上部署ASP.NET MVC
- nakadi 一款基于kafka 的http event broker
- onunload事件火狐不支持，在IE浏览器中，只有刷新时该事件才发生
- 4.3 Routing -- Generated Objects
- Android手机无线adb
- 《js笔记》