上一篇主題 :: 下一篇主題 |
發表人 |
內容 |
tuberose
註冊時間: 2006-05-02 文章: 33
第 16 樓
|
發表於: 星期六 五月 09, 2015 5:29 pm 文章主題: |
|
|
第 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) + " 秒" |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 17 樓
|
發表於: 星期六 五月 09, 2015 5:29 pm 文章主題: |
|
|
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 在 星期六 五月 09, 2015 5:40 pm 作了第 2 次修改 |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 18 樓
|
發表於: 星期六 五月 09, 2015 5:30 pm 文章主題: |
|
|
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 在 星期六 五月 09, 2015 5:39 pm 作了第 2 次修改 |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 19 樓
|
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
ckp6250
註冊時間: 2004-07-30 文章: 1645
第 20 樓
|
發表於: 星期六 五月 09, 2015 5:40 pm 文章主題: |
|
|
目前看來 , tuberose 是最快的了
在我的電腦 , 1-100萬 , 只要 0.54秒
我們之前的運算,都是加法,
tuberose 的卻是用減法
坦白說,運算原理我還沒完全理解
別出新裁 , 折服。
可否請tuberose解釋一下運算模式 |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 21 樓
|
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
perry
註冊時間: 2014-07-20 文章: 203
第 22 樓
|
發表於: 星期六 五月 09, 2015 6:02 pm 文章主題: |
|
|
用排除倍數法,沒有多餘的運算判斷果然快速!!
陣列數就是數值1~n,去掉1及所有倍數值 .t.,
剩下就是質數^^ |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 23 樓
|
發表於: 星期六 五月 09, 2015 6:12 pm 文章主題: |
|
|
正则表达式也可以计算质数
但速度不快
=====================
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) + " 秒" |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 24 樓
|
發表於: 星期六 五月 09, 2015 6:14 pm 文章主題: |
|
|
陣列數只能计算到一亿
这个是限制 |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
tuberose
註冊時間: 2006-05-02 文章: 33
第 25 樓
|
發表於: 星期六 五月 09, 2015 8:48 pm 文章主題: |
|
|
逆向计算
*!* 求前 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)) |
|
回頂端 |
|
![](templates/subSilver/images/spacer.gif) |
|