PTT數位生活區 / C_and_CPP (C/C++)

[語法] 質數

看板C_and_CPP (C/C++)作者 (jordan)時間16年前 (2010/04/27 13:27), 編輯推噓5(5推 0噓 6→)
留言11則, 6人參與, 最新討論串1/1
請問有沒有什麼方法能很快的求出質數的個數 使用過了6n+1和 sieve 只是6n+1不夠快 sieve又MLE 不知道有什麼方法 範圍是從1-10000000 可問至多10000個問題 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.70.137.251
推
04/27 13:29, , 1F
建表建小一點 (根號10^7), 問超出建表範圍的再用質數表去除
04/27 13:29, 1F
推
04/27 13:48, , 2F
MLE? 哪一題呢?
04/27 13:48, 2F
→
04/27 14:14, , 3F
建到 10000000^1/2 (大概3162) 的表就可以了
04/27 14:14, 3F
推
04/27 15:53, , 4F
不負責任猜測是10311
04/27 15:53, 4F
→
04/27 15:53, , 5F
04/27 15:53, 5F
推
04/27 20:37, , 6F
MLE就把偶數踢掉就好 不然位元壓縮一下
04/27 20:37, 6F
→
04/27 20:37, , 7F
再不行乾脆把空間 /3/8 算了……
04/27 20:37, 7F
→
04/28 01:31, , 8F
那題的話, 建 100,000,000/8 個 bytes 的表 (大概12MB)
04/28 01:31, 8F
→
04/28 01:32, , 9F
做 sieve ，40MB 應該綽綽有餘了？
04/28 01:32, 9F
→
04/28 11:54, , 11F
10311時間3秒內，40MB很足夠了。
04/28 11:54, 11F
‣ 更多 michael12348 的文章
文章代碼(AID): #1BrdMemP (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 michael12348 的文章
文章代碼(AID): #1BrdMemP (C_and_CPP)