#22031: oz_求更好的解法，還有篩質數請用埃拉托斯托尼篩法，會快很多喔~

學校 : 臺北市立建國高級中學
編號 : 95399
來源 : [111.248.226.38]
最後登入時間：
2024-11-10 00:36:50

a505. B. T-primes -- CodeForce 230B T-primes | From: [61.230.19.145] | 發表日期 : 2020-08-10 22:39

這題有夠煩...

其實就是找出小於10^7的所有質數的完全平方數

但數字、測資很大，有夠讓人不爽...

這題我本來是建小於sqrt(10^7)的質數表，再對輸入的數sqrt()後做質因數分解，但太慢了...

後來改成建小於sqrt(10^7)的質數表，再對輸入的數sqrt()後做質數判別，過的了第一個，但對第二個側資站來說還是太慢了...

我再改成以下方法

步驟1(篩質數).直接從2跑到10000000，看一個數可不可以被在比他的平方根還小的質數整除，不行被任何比他的平方根還小的質數給整除，就將它紀錄在質數表。

步驟2(找平方數):設一個set，把每個質數表裡的質數平方後放進去

步驟3:讀入廁資，用set裡的find來確定是否為質數的平方

結果還是TLE...

後來不用步驟1的篩法，改成sieve of eratosthenes，就壓線過了...

所以篩質數請用sieve of eratosthenes也就是埃拉托斯托尼篩法

後來我再加點優化就可以縮到0.2s了

#22034: Re:oz_求更好的解法，還有篩質數請用埃拉托斯托尼篩法，會快很多喔~

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間：
2024-11-10 10:25:04

a505. B. T-primes -- CodeForce 230B T-primes | From: [36.227.187.5] | 發表日期 : 2020-08-11 00:17

原文吃掉。

ZeroJudge Forum