發表新討論
#17981: 不用建表也能過的方法


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

a007. 判斷質數 | From: [114.42.216.150] | 發表日期: 2019-06-07 18:58

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

除了2和3

一個想法

 

只要6n不是平方數

6n+1

6n -1

必為質數

 

 

#17985: Re:不用建表也能過的方法


inversion (「我們所認識的可符香是個像天使的好女孩」之葉林 *Cries...)

a007. 判斷質數 | From: [49.158.83.43] | 發表日期: 2019-06-07 20:23

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

除了2和3

一個想法

 

只要6n不是平方數

6n+1

6n -1

必為質數

 

 

不好意思潑個冷水，您的敘述是有誤的：

 

在 6n 不是平方數的狀況下，6n + 1、6n - 1 依然並不保證是質數，例如： 25 （6 × ４ + 1） 、 49 （6 × 8 + 1）、 …… 、 119 （6 × 20 - 1） 、 121 （6 × 20 + 1）等等。

且因為剔除了 6n 為平方數的狀況，使得某些質數不會被判斷到，例如： 37 （6 × 6 + 1）、1297（6 × 216 + 1）等等

 

以上。

#17987: Re:不用建表也能過的方法


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

a007. 判斷質數 | From: [114.42.216.150] | 發表日期: 2019-06-08 09:52

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

除了2和3

一個想法

 

只要6n不是平方數

6n+1

6n -1

必為質數

 

 

不好意思潑個冷水，您的敘述是有誤的：

 

在 6n 不是平方數的狀況下，6n + 1、6n - 1 依然並不保證是質數，例如： 25 （6 × ４ + 1） 、 49 （6 × 8 + 1）、 …… 、 119 （6 × 20 - 1） 、 121 （6 × 20 + 1）等等。

且因為剔除了 6n 為平方數的狀況，使得某些質數不會被判斷到，例如： 37 （6 × 6 + 1）、1297（6 × 216 + 1）等等

 

以上。

我其實發完就有發現

難怪我過不了

但我後來又改了

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

可達到

 

AC (1.8s, 376KB)

這樣就能過了

#17991: Re:不用建表也能過的方法


icube (!@#$%^&*()_+)

a007. 判斷質數 | From: [220.135.116.184] | 發表日期: 2019-06-08 10:46
 

我其實發完就有發現

難怪我過不了

但我後來又改了

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

可達到

 

AC (1.8s, 376KB)

這樣就能過了

加那兩行可能從TLE變成AC，但問題在於你採用一個錯誤的質數判斷法。

#17996: Re:不用建表也能過的方法


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

a007. 判斷質數 | From: [114.42.216.150] | 發表日期: 2019-06-08 12:05
 

我其實發完就有發現

難怪我過不了

但我後來又改了

cin,cout加上
cin.tie(0);
ios::sync_with_stdio(false);

可達到

 

AC (1.8s, 376KB)

這樣就能過了

加那兩行可能從TLE變成AC，但問題在於你採用一個錯誤的質數判斷法。


sorry

我講得有點怪

應該是

我改了一些地方

答案正確了

但又TLE

所以加上
cin.tie(0);
ios::sync_with_stdio(false);

就

AC (1.8s, 376KB)

---------------------------------

其實6n+1

還是不錯用的

可以刷掉大部分數字

剩下就要靠其他判斷法了

ZeroJudge Forum