VFP 愛用者社區

[tuberose]

第 15 樓 的我的 PC 机运行 16秒
下面的要 2.5秒

========================================
*!* 100万以内的质数，2.5秒

Clear
T1 = Seconds()
num = 1000000
Local azs[num]
lncnt = num - 1
For lnI = 2 To Int(Sqrt(num))
If azs[lnI] = .F.
For lnJ = lnI * lnI To num Step lnI
If azs[lnJ] = .F.
azs[lnJ] = .T.
lncnt = lncnt - 1
Endif
Endfor
Endif
Endfor
t2 = Seconds()
? "(1 - " + Transform(num) + ") 之间共有质数 " + Transform(lncnt) + " 个"
? "共运行：" + Transform(Seconds() - t1) + " 秒"

[tuberose]

Clear
m.Max = 1000000 && --> 78498, 2%5E100
* m.Max = 78498 && --> 7702

lnSec = Seconds()
oXMLHTTP = Createobject("MSXML2.XMLHTTP")
oXMLHTTP.Open("Get", "http://www.wolframalpha.com/input/?i=primes+less+than+" + Alltrim(Str(m.Max)), .T.)
* or http://www.wolframalpha.com/input/?i=primes+less+than+2%5E10
* or http://www.wolframalpha.com/input/?i=primes+between+100%2C000+and+101%2C000&lk=3

oXMLHTTP.setRequestHeader("Content-type", "application/x-www-form-urlencoded")
oXMLHTTP.setRequestHeader("Content-type", "text/xml; charset=utf-8")
oXMLHTTP.setRequestHeader("Connection", "Close")

oXMLHTTP.Send(.Null.)

Do While oXMLHTTP.readyState != 4
=Inkey(0.1)
Enddo

If oXMLHTTP.Status = 200
cStr = oXMLHTTP.ResponseText
m.Prime = Strextract(cStr, "Prime[Range[1,", "]]") && "Prime[Range[1, 78498]]"
? m.Prime
Endif
? Seconds() - lnSec

[tuberose]

Clear
m.Max = 1000000 && --> 78498, 2%5E100
* m.Max = 78498 && --> 7702

lnSec = Seconds()
oXMLHTTP = Createobject("MSXML2.XMLHTTP")
oXMLHTTP.Open("Get", "http://api.wolframalpha.com/v2/query?appid=KHE5G2-42E4UX5AL3&input=primes <= " + Alltrim(Str(m.Max)) + ")&format=image,plaintext", .T.)

oXMLHTTP.setRequestHeader("Content-type", "application/x-www-form-urlencoded")
oXMLHTTP.setRequestHeader("Content-type", "text/xml; charset=utf-8")
oXMLHTTP.setRequestHeader("Connection", "Close")

oXMLHTTP.Send(.Null.)

Do While oXMLHTTP.readyState != 4
=Inkey(0.1)
Enddo

If oXMLHTTP.Status = 200
o = Createobject("Microsoft.XMLDOM")
o.LoadXML(oXMLHTTP.ResponseText)
plaintext = o.documentElement.getElementsByTagName('plaintext')
For I = 0 To plaintext.Length - 1
? plaintext.Item(I).Text && plaintext
Next
Endif
? "Elapsed time : " + Transform(Seconds() - lnSec)


Return

[tuberose]

用 primesieve 3.6
计算 100亿的质数，秒杀。
Homepage: http://primesieve.googlecode.com

[ckp6250]

目前看來 , tuberose 是最快的了
在我的電腦 , 1-100萬 , 只要 0.54秒

我們之前的運算,都是加法,
tuberose 的卻是用減法
坦白說，運算原理我還沒完全理解
別出新裁 , 折服。

可否請tuberose解釋一下運算模式

[tuberose]

使用 Sieve of Eratosthenes 算法
Web at : http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[perry]

用排除倍數法,沒有多餘的運算判斷果然快速!!
陣列數就是數值1~n,去掉1及所有倍數值 .t.,
剩下就是質數^^

[tuberose]

正则表达式也可以计算质数
但速度不快

=====================
nPrime = 10000 && >= 1 / 10,000 约 44秒

tStartTime = Seconds()
oRE = Createobject("VBScript.RegExp")
oRE.Pattern = "^1?$|^(11+?)\1+$" && 判别质数模板
nCount = 0
cPrime = "1"
For I = 1 To nPrime
* llReturn = oRE.Test(Replicate("1", I))
llReturn = oRE.Test(cPrime)
cPrime = cPrime + "1"
If !llReturn
nCount = nCount + 1
Endif
Endfor
? "总数 : " + Transform(nCount) + " (1 - " + Transform(nPrime) + ")"
? "耗时 : " + Transform(Seconds() - tStartTime) + " 秒"

[tuberose]

陣列數只能计算到一亿
这个是限制

[tuberose]

逆向计算
*!* 求前 X 个质数的自然数范围
*!* 1,000,000 耗时1.5秒

Clear
lnSec = Seconds()
lnCnt = 74300
lnOddArea = Int(1.2*lnCnt*Log(lnCnt)/2)
Local aDigits(lnOddArea)
k=1

For i = 1 To lnOddArea
If aDigits[i]
Loop
Endif

For j = (i+1)*i*2 To lnOddArea Step 2*i+1
aDigits[j] = .T.
Endfor
k=k+1

If k=lnCnt
Exit
Endif
Endfor

Local primes(78499)
primes(1) = 2
j = 2

For i = 1 To Alen(aDigits)
If !aDigits(i)
primes(j) = 2*i+1
j = j+1
Endif

Next

? "前 " + Transform(lnCnt) + " 个质数是自然数的 " + Transform(2*i+1)
? "耗时 : " + Transform(Seconds() - lnSec) + " 秒"
? "================================="
? "前 168 个质数是自然数的 " + Transform(primes(168))