无聊之中，做了一个质数判断，尚待完善

aoe1981

pt98 发表于 2014-1-19 21:18
'找了个c代码稍作修改，10000000之内耗时0.7s
Option Explicit
Const N  As Long = 10000000

　　研究了半天，确实巧妙！得出了很有用的结论，在1到1000 0000里素数一共有66 4579个，而且全部都能找出来，一古脑儿可以都列举出来，实在妙啊！！！也说明，在1到1千万里，素数的稠密度约是6.6%！
　　问题有二：
　　1、不能对一个合数进行因数分解，与我的初衷有点不一样，这是思考问题的角度和问题方向的不同造成的；
　　2、但不知Excel VBA中一维数组变量最大的上标是多少，这个如果有限制的话，会影响程序的应用！

aoe1981

northwolves 发表于 2014-1-19 22:40
更多资源，可参考：http://en.wikipedia.org/wiki/Prime_factorization

多谢指点，29楼的代码一会研究，这个资源又是英文，真是越发感觉知识不足、能力不够、见识不广啊！刚才一直在研究27楼的代码。。。

aoe1981

pt98 发表于 2014-1-19 21:18
'找了个c代码稍作修改，10000000之内耗时0.7s
Option Explicit
Const N  As Long = 10000000

我测试到的一维数组最大上标是9637 0679，运行了24秒，得出素数个数556 4258，稠密度约5.77%。上标为9637 0680也即再加1时，程序出错，显示“内存溢出”！得出的素数多，但时间优势开始不明显，同时也不能解决大数据的问题。。。

northwolves

这个问题已经研究的很多，参考：

http://oeis.org/A004023

northwolves

2     11=11
(is a prime)

3     111=3*37

4     1111=11*101

5     11111=41*271

6     111111=3*7*11*13*37

7     1111111=239*4649

8     11111111=11*73*101*137

9     111111111=3*3*37*333667

10     1111111111=11*41*271*9091

11     11111111111=21649*513239

12     111111111111=3*7*11*13*37*101*9901

13     1111111111111=53*79*265371653

14     11111111111111=11*239*4649*909091

15     111111111111111=3*31*37*41*271*2906161

16     1111111111111111=11*17*73*101*137*5882353

17     11111111111111111=2071723*5363222357

18     111111111111111111=3*3*7*11*13*19*37*52579*333667

19     1111111111111111111=1111111111111111111
(is a prime)

20     11111111111111111111=11*41*101*271*3541*9091*27961

21     111111111111111111111=3*37*43*239*1933*4649*10838689

22     1111111111111111111111=11*11*23*4093*8779*21649*513239

23     11111111111111111111111=11111111111111111111111
(is a prime)

24     111111111111111111111111=3*7*11*13*37*73*101*137*9901*99990001

25     1111111111111111111111111=41*271*21401*25601*182521213001

26     11111111111111111111111111=11*53*79*859*265371653*1058313049

27     111111111111111111111111111=3*3*3*37*757*333667*440334654777631

28     1111111111111111111111111111=11*29*101*239*281*4649*909091*121499449

29     11111111111111111111111111111=3191*16763*43037*62003*77843839397

30     111111111111111111111111111111=3*7*11*13*31*37*41*211*241*271*2161*9091*2906161

31     1111111111111111111111111111111=2791*6943319*57336415063790604359

32     11111111111111111111111111111111=11*17*73*101*137*353*449*641*1409*69857*5882353

33     111111111111111111111111111111111=3*37*67*21649*513239*1344628210313298373

34     1111111111111111111111111111111111=11*103*4013*2071723*5363222357*21993833369

35     11111111111111111111111111111111111=41*71*239*271*4649*123551*102598800232111471

36     111111111111111111111111111111111111=3*3*7*11*13*19*37*101*9901*52579*333667*999999000001

37     1111111111111111111111111111111111111=2028119*247629013*2212394296770203368013

38     11111111111111111111111111111111111111=11*909090909090909091*1111111111111111111

39     111111111111111111111111111111111111111=3*37*53*79*265371653*900900900900990990990991

40     1111111111111111111111111111111111111111=11*41*73*101*137*271*3541*9091*27961*1676321*5964848081

41     11111111111111111111111111111111111111111=83*1231*538987*201763709900322803748657942361

42     111111111111111111111111111111111111111111=3*7*7*11*13*37*43*127*239*1933*2689*4649*459691*909091*10838689

43     1111111111111111111111111111111111111111111=173*1527791*1963506722254397*2140992015395526641

44     11111111111111111111111111111111111111111111=11*11*23*89*101*4093*8779*21649*513239*1052788969*1056689261

45     111111111111111111111111111111111111111111111=3*3*31*37*41*271*238681*333667*2906161*4185502830133110721

46     1111111111111111111111111111111111111111111111=11*47*139*2531*549797184491917*11111111111111111111111

47     11111111111111111111111111111111111111111111111=35121409*316362908763458525001406154038726382279

48     111111111111111111111111111111111111111111111111=3*7*11*13*17*37*73*101*137*9901*5882353*99990001*9999999900000001

49     1111111111111111111111111111111111111111111111111=239*4649*505885997*1976730144598190963568023014679333

northwolves

楼主可用数组只保存得到的素数，10^8内只有5761455个素数。10^9内也只有50847534个

算法的优化可参考：http://bbs.emath.ac.cn/thread-234-1-1.html

northwolves

少量素数的筛选最常用的还是Eratosthenes筛选法，可参考拙作：

http://blog.csdn.net/northwolves/article/details/351998
http://blog.csdn.net/northwolves/article/details/532695
http://blog.csdn.net/northwolves/article/details/533038

如果只是判断一个数字的素性，可使用一些素性判定法，如：米勒-拉宾素数判定法，不妨google搜之

香川群子

楼主研究的问题有2个方面吧：

1. 求1-n之间所有的素数

2. 求n的素数因数分解结果(并依此判断是否素数)

hnwxm

用产生素数表的方法即可，当然可以再提速，一般讲没必要。

aoe1981

香川群子 发表于 2014-1-20 09:17
楼主研究的问题有2个方面吧：

1. 求1-n之间所有的素数

研究不敢当，业余的，兴趣也是需要付出代价的。。。主要目的是2，1算是受了坛内高手的启示吧。。。我本想随便输入一数，可以判断其素性，若不是素数，能给出因数分解式就行。。。没多少学术上的目的。。业余的，偶然间起意的。。。过过时间，呵呵