编程挑战题幸运数有关问题解决思路（神秘算法，空间换时间，多线程？）

编程挑战题幸运数问题解决思路（神秘算法，空间换时间，多线程？）
1.考虑到10个以内个位数之和，10个以内个位数平方和不会超出1000，先求出1000以内的素数，生成一个由0和1构成的数组，0代表合数，1代表质数。
关键代码如下：

void makeList(){

	int a,b,num;

	plist[2]=1;

	plist[3]=1;

	for(int i=6;i<1000;i+=6){

		a=i-1;

		b=i+1;

		bool flag1=true;

		bool flag2=true;

		num=static_cast<int>(sqrt(static_cast<double>(i)));

		for(int j=2;j<=num+1;j++)

		{

			if(a%j==0)

			{

				flag1=false;

				break;		   

			}

			if(b%j==0)

			{

				flag2=false;

				break;

			}	  

		}

		if(flag1)

		{

			plist[a]=1;

		}

		if(flag2)

		{

			plist[b]=1;

		}

	}


}

素数表生成之后，判断各位和 ，平方和是否是素数所需时间可以忽略，就是索引数组的值。基本上没有比这更快的方法了

inline int isPrime(int index){

return plist[index];

}

2.10亿次循环，一般pc单线程不能在3s内完成，可以写多线程程序，每个线程计算一部分，计算完毕结果累加。我电脑core i5 双核四线程 ，四线程全开的话，每个线程平均计算2.5亿次，3s内完成，也不是一般人就能轻轻松松做到的。
3.尽量减少循环数，这10亿个数，有没有什么规律能够剔除一些！！！比如数学上的某种规律！！！！请挑战成功的大神们不吝赐教一下，挑战结果无关紧要，重要的是我们要成长呀。
十分期待有神秘算法的出现！
4. 我这个笨脑袋能想到的就是把1-1亿，1亿-2亿，2亿-3亿....
有多少幸运数先求出来，比如
[1-1亿) 10442844个 
[1亿-2亿) 10422480个
[2亿-3亿) 10587064个 
[3亿-4亿) 10249546个 
.....
每个区间先求出来生成一个静态数组，根据区间运算大大的减少了运算量。
比如320000000-830000000，可转换为，先计算3亿到3亿2千万的幸运数的数量，用3亿到4亿的数量减去它，即3亿2千万到4亿幸运数的数量，加上相隔区间的幸运数的数量5,6,7,8亿...加上8亿到8亿3千万的幸运数的数量，最终可以求得320000000-830000000幸运数的数量。运算量只有几千万。

------解决方案--------------------
只是统计个数，简单DP一下就好了。一点也不神秘。
------解决方案--------------------
看看这个对你有用否
http://blog.****.net/shuyechengying/article/details/9164517
------解决方案--------------------
http://bbs.****.net/topics/390499128
相同的问题