估算一下驗(yàn)證一個(gè)100位的10進(jìn)制整數(shù)是否是質(zhì)數(shù)在當(dāng)前的計(jì)算機(jī)上需要多少時(shí)間

benlan

在一個(gè)網(wǎng)站上的看到的兩個(gè)題目，未想出好的方法，求解

1. 估計(jì)一下全球60億人口中和你在同年、同月、同日、同一個(gè)小時(shí)內(nèi)（比如都在8:00-9:00之間）出生的有幾個(gè)人？說出你的依據(jù)。
2. 估算一下驗(yàn)證一個(gè)100位的10進(jìn)制整數(shù)是否是質(zhì)數(shù)在當(dāng)前的計(jì)算機(jī)上需要多少時(shí)間。請給出分析過程。

熊貓燒香

（1）可以把全世界的人口出生狀況看作是一個(gè)概率分布，如均勻分布。
再按照時(shí)間來計(jì)算概率密度。具體的可以參看人口數(shù)學(xué)的相關(guān)內(nèi)容。
（2）質(zhì)數(shù)的判定有很多概率的方法，速度很快的。
100位不成問題。你可以在網(wǎng)上找找。

ArXoR

原帖由 benlan 于 1/31/07 09:46 發(fā)表
在一個(gè)網(wǎng)站上的看到的兩個(gè)題目，未想出好的方法，求解

1. 估計(jì)一下全球60億人口中和你在同年、同月、同日、同一個(gè)小時(shí)內(nèi)（比如都在8:00-9:00之間）出生的有幾個(gè)人？說出你的依據(jù)。
2. 估算一下驗(yàn)證一個(gè)100位的 ...

第二個(gè)問題AKS可在O((logn)^6)內(nèi)確定判定, 搜論文 Prime is in P