[問題] 老梗的質數問題

[cory8249 (Cory)]

Code: http://pastie.org/2022517

老梗的質數問題

因為數字稍大  (1,000,000)

所以必須盡量有效率點

經過爬文後

已經優化的部分如下:

1. 建立質數表,滿足題目多次查詢的需求

2. 迴圈變化 i=i+2  砍掉2的倍數

3. 只使用質數表內的質數驗證

4. 用 x*x > i 取代 x > sqrt(i)  減少運算複雜度

5. cin / cout 改成 printf / scanf 加快讀寫速度




目前單純跑質數表是 0.35 秒

應該不算太慢

但是題目有點機車

會餵大量的數字

導致最後都會超過 1 秒的時間限制

(數字小量就可以AC)


所以想請教各位

這樣的算法還是否能改進 ??

或是說直接重寫成 "刪去法" 會比較好呢 ?

還是根本是我們老師弄的 Online Judge 設計不良 ?   (目前無人通過)



以上

感謝各位的協助~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.233.233
→ chihungtzeng:質數表建完後用 binary search 查是不是質數
恩  來研究一下好了

(小弟新手)

→ loveme00835:同樓上, 全找出來試試
→ tkcn:都有 prime_v 了，連 binary search 都不用才對
用 二分搜尋法 去找 好像比較快的樣子 ?

→ loveme00835:疑, 沒看到 XD
→ loveme00835:if(prime_v[i]*prime_v[i]>k) break; 改掉先用一個變
→ loveme00835:數存k開根號的結果, 直接prime_v[i]跟root_of_k比
剛剛改了~但是效果好像不明顯

→ tkcn:能改進的其實還很多 :p
煩請煩高手指點了

→ loveme00835:inner loop跑的次數太多了, 到root_of_k就好, 不要把
→ loveme00835:所有輸入都存起來, 每讀一個馬上輸出結果就好
可是題目規定要先全部輸入再輸出
※ 編輯: cory8249        來自: 111.255.233.233      (06/05 23:13)
→ firejox:才10^6而已 就用Eratosthenes篩法就好了呀
恩 那我重寫一個試試看好了

→ loveme00835:除非它是測你輸入的時間點跟輸出時間點, 否則都是用IO
→ loveme00835:重導向, 最後程式結束作檔案比對而已
原來如此... 恕小弟無知 >"<
※ 編輯: cory8249        來自: 111.255.233.233      (06/05 23:26)
※ 編輯: cory8249        來自: 111.255.233.233      (06/05 23:27)
推 suhorng:開一個 1000001 的陣列, 把質數對應的項目標示出來
→ suhorng:這樣對於每個詢問 直接查詢對應的項目是否有被標記就好
→ loveme00835:樓上說的像是: bool is_prime[1000001]; [0] [1]不用
終於AC了   !!

非常感謝各位的幫忙
※ 編輯: cory8249        來自: 111.255.233.233      (06/05 23:46)
推 tropical72:>> 用 x*x > i 取代 x > sqrt(i)
→ tropical72:沒人懷疑過這點嗎?這部份我實際上傳是較慢的.
→ tropical72:最後是用 target = (int)ceil(sqrt((double)x)));
→ firejox:篩法：git://gist.github.com/1009686.git
→ firejox:其實我覺得改那部份不會快多少@@
→ firejox:x*x>i的部份
推 yoco315:大數字用 Miller-Rabin test 測 2 7 61 XD 神速
→ yoco315:Miller-Rabin test http://tinyurl.com/3pmvojz
→ firejox:回yoco大 樓上的wiki似乎被砍掉了@@
推 tropical72:Miller-Rabin, 拙著 : http://ppt.cc/oneJ
推 cole945:可以直接完算78500個質數塞進source code嗎XD?
→ tropical72:@cole945: stack 恐沒那麼大可以塞
推 cole945:塞global呀. 而且原本的prime_v就已經是local變數了呀 囧