很老的问题了，求素数的问题。高手们请给个提示。谢谢！！！！！！！！！！！
求10的10次方内的素数。
小弟用的算法太屎了，10分钟才能算到20000000。
晕，我知道一定有好的算法的。
我是定义了一个long型数组来存储的，我知道用数组是很占内存的，而且100000000——10000000000是用求余数再除的方法，呵呵，是不是太笨了呀！
各位大虾，我是个大菜鸟，谢谢帮助！
问题点数：20、回复次数：6Top
1 楼hanyixin（怡）回复于 2003-12-03 08:58:34 得分 2
筛子法呀，呵呵。
Top
2 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-12-03 09:07:59 得分 2
最快的办法就是预先建立一个素数表，然后到里面去查Top
3 楼guyu412（谷雨）回复于 2003-12-03 09:14:46 得分 2
不知道有什么好办法，你可以把最后一位是偶数的去掉。可以去掉一半，不知会不会快点。Top
4 楼klbt（快乐白兔）回复于 2003-12-03 09:18:25 得分 2
呵呵，你只需要建立一个小于100000的素数表，即可判断。Top
5 楼lhlemail（就随风）回复于 2003-12-03 09:46:43 得分 2
可以利用空间换时间，
建立两个动态数组一个用来存储素数，一个用来存储与每一个素数比较的比较数，
当比较数与对应的素数相等时，则将其置零重新累计。这样会缩短不少时间。
Top
6 楼byyyyy（苦行僧【苦】）回复于 2003-12-03 10:11:15 得分 10
除２这个特别的素数外，所有的素数都可以分成两类：第一类是被４除余１的素数，如５，１３，１７，２９，３７，４１；第二类是被４除余３的素数，如３，７，１１，１９，２３，３１。第一类素数都能表示成两个整数的平方和（第二类则不能）。
例如：５＝１＊１＋２＊２１３＝２＊２＋３＊３１７＝１＊１＋４＊４２９＝２＊２＋５＊５这就是著名的费尔马“二平方”定理。有趣的是：上述等式右侧的数有的又恰恰是两个素数的平方，如１３、２９的表达式，叫作费尔马“二平方”素数，即如果一个素数能够表示成两个素数的平方和的形式：Ｆ＝Ｘ＊Ｘ＋Ｙ ＊Ｙ （１）其中Ｆ、Ｘ、Ｙ 都是素数，它就是费尔马“二平方”素数。
因此你可以现将偶数去掉，然后按照上面分成的这两类进行一下求解。
而且n无穷大时,高斯猜测，n以内的素数个数大约与n/lnn相当，或者说，当n很大时，两者数量级相同。这就是著名的素数定理。可以验证一下。
不知道我的理解对不对，欢迎讨论！Top
