Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 7 years ago

Zerojudge a007: 判斷質數(C++)

各位高手:

請問一下,這一個判斷質數的問題到底要怎樣才能不逾時呢?

我已經試到快瘋了!

(而且老師又沒教怎麼建立質數表......)

題目在這裡:

http://zerojudge.tw/ShowProblem?problemid=a007

我的答案(這是我想到最快的方法了):

#include

using namespace std;

int prime(int n);

int main()

{

int i;

while(cin>>i)

{

if(prime(i)) cout<<"質數"<

else cout<<"非質數"<

}

}

int prime(int n)

{

if(n==2 || n==3) return 1;

if(n%6==0 || n%6==2 || n%6==3 || n%6==4) return 0;

for(int i=5;i*i<=n;i+=2)

if(n%i==0) return 0;

return 1;

}

Update 2:

有哪位高手可以用Miller-Rabin測試法以C++的形式寫給我看?

網路上看到的都是C語言......

Update 3:

G,您好:

這一題在最近有更新過,我原本也是用您的方法喔!

但是就是會逾時......

想請問一下

#include

的功用是甚麼呢?

另外,我覺得您的寫法跟我的好像喔!

該不會我們是同一個陣營出來的吧!

哈哈!

Update 4:

Scoot,您好:

謝謝您的建議。

可是我不會建質數表耶!

(我只是一個剛學C++的高中生)

可以跟我說哪裡有建質數表的教學嗎?

8 Answers

Rating
  • 7 years ago
    Favorite Answer

    同學建議你先寫別題

    我記的我 Miller-Rabin 沒過

    如各位所知,ZJ上不少好題目,也不少屁還

    本題a007 Jiangsir 出的怎麼可能會惡整大家!! (而且又在基礎題庫

    是因為有屁孩"管理員" 改Jiangsir 測資

    所以這題失去 "基礎"意義

    畢竟這裡是公開場合我並不大算給程是碼

    HINT:

    先建 質數表 到 46341 (WHY?? -> 46341 = 根號2147483647

    接下來每讀一個數 判斷一次

    我的ZJ ID:scott

    如果真想不出來 寄訊息給我

  • 7 years ago

    稍微問一下

    到46341的質數表我會做

    可是要怎麼判斷大於46341的數是不是質數?

    2014-04-27 21:02:07 補充:

    果不其然0..0

    TLE...

    2014-04-27 21:04:18 補充:

    這是我的code

    http://codepad.org/fAUmVkXG

  • 7 years ago

    #include<iostream>

    #include<cstdlib>

    #include<cmath>

    using namespace std;

    int main(){

    int a;

    while(cin>>a){

    int tag=1;

    for(int i=2;i<=sqrt(a);i++){

    if(a%i==0){

    tag=0;

    break;

    }

    }

    if(tag==0){

    cout<<"非質數"<<endl;

    }else{

    cout<<"質數"<<endl;

    }

    }

    system("pause");

    return 0;

    }

    我看了你的方法,

    先行否定2和3的確是當測資為2或3時會減少執行時間

    但是這樣故意去管特例的方法有個問題

    當測資不是2或3時,他反而會增加程式的執行時間

    感覺第二個if也有這樣的問題

    最好是能有一個概括所有狀況的程式碼

    還有這樣兩個if 篩選時要特別小心邏輯會不會有漏洞

    目前我看應該是沒有

    我的方法和你顛倒

    你把可能得因數乘倍對n處理

    我則是把n開根號而因數從2開始跑

    ("sqrt"是"cmath"函式庫裡的函式,關於cmath你可以多多研究,功用很大)

    這程式碼是我當初解這題時用的記錄,大約是2年前寫的

    我直接貼上來沒做檢查,如果有問題可以在聯絡我

    2014-02-06 12:16:15 補充:

    啊啊,貌似現在我也過不了了呢

    抱歉,如果最近我有寫通過會通知你的

    不過你可以多上網查找資料,不光是程式部分

    一些數學定理也可以閱讀看看,像是費馬定理、勒真德公式等

    應該會用得上

    include是載入函式庫

    看你得程式碼,你應該有自定義函是的概念了

    那你可以想想看,為什麼cin、cout這些卻不用自定義就可以直接使用了呢?

    函式庫是一個函式的集合(想像網路上的懶人包)

    而上面我呼叫了三個函式庫

    (包含了很多關於標準輸入輸出的函式)

    (包含了一些較為進階的功能)

    (包含數學進階運算的函式)

    Source(s): 自己的編程經驗, 網路資料
  • re
    Lv 4
    7 years ago

    提供查表的寫法

    http://paste.ideaslabs.com/show/WDJDMNlpU

    2014-02-06 21:16:41 補充:

    其實原提問所引用的網站已經有程式碼了

    只是少了pow跟mul函數的實作,補上後即可運作

    (下列網址為同一行,不知道為何要分成兩行才貼得出來)

    https://googl/

    edrive.com/host/0B7BQDCTnNN42UUphSTdQcE5qY1k/prime.html

    ps.實作這兩個函數,需注意溢位問題及是否可以有O(logN)的效率

    2014-02-11 15:54:07 補充:

    Leo,之前不知道你剛學,前面我寫的就當做參考,有空再看即可。

    針對「不知道如何建立質數表」的問題,這其實是陣列的應用,不知道你學過了沒?如果學過可以先想想要怎麼作。

    程式只是把想法交給電腦工作的語言而已,所以首先要先有解題想法。既然只是應用,老師自然不會教怎麼做了。

    因為快要到期了,我就先貼上解題想法了,要是想不出來可以當參考。

    http://re_web.droppages.com/prime_table.html

    (這次總貼得出來了吧)

  • How do you think about the answers? You can sign in to vote the answer.
  • 7 years ago

    這題的確有誇張到..

    之前寫的時候也卡了很久

    之後就放著了

    現在那題還是空著的..

  • 7 years ago

    你知道 C++ 是延伸物件........所以?若要造成「演算法」,其實?並不然!

    因為延伸物件上?能夠完成其他事情。

  • Anonymous
    7 years ago

    Primality Test: Miller-Rabin Algorithm

    http://www.csie.ntnu.edu.tw/~u91029/Prime.html#5

    2014-02-02 19:49:45 補充:

    嗯,我的意思是說我看不懂#include

    學校老師只有教#include

    我才剛開始學習而已......

    2014-02-02 19:50:38 補充:

    我的意思是說我看不懂#include stdio.h

    學校老師只有教#include iostream

    2014-02-02 19:53:38 補充:

    謝謝提醒,那個我知道

    我是看這裡得知這個訊息的

    http://www.csie.ntnu.edu.tw/~u91029/Prime.html#5

    他這裡有說到:

    「事實上已經有熱心人士,找出特定的底數組合,仔細檢查了各種數字的判定結果,保證判定結果正確。例如底數組合 {2, 7, 61} 就能正確判斷 2^32 以下的數字是不是質數。」

    2014-02-03 00:30:30 補充:

    To A TK UE 2AEO OR UFO:

    謝謝囉!我先研究看看……

    To DarkMan:

    什麼意思?我不太懂……

    2014-02-03 22:13:38 補充:

    A TK UE 2AEO OR UFO,您好:

    我拿去測試這題,它說編譯錯誤耶!

    2014-02-04 11:08:24 補充:

    謝謝您!

    我等一下試試看!

    2014-02-05 13:29:27 補充:

    謝謝!

    這個我比較看得懂......

    2014-02-07 13:15:35 補充:

    跳過二的倍數之後還是會TLE…

    2014-02-07 13:18:37 補充:

    re,辛苦您了!

    Yahoo!和Google是對手

    如果打到Google等字眼就會違規喔!

    2014-02-17 22:12:04 補充:

    可以等到這一題我真的解出來在選最佳解答嗎?

    要是到時候回答者和意見者都有不錯的方法的話,我會再開一題讓大家回答!

    2014-04-27 20:38:28 補充:

    就是用你建出來的表去跑,如果這些質數都不是它的因數的話,那麼這個數肯定會是一個質數。

    2014-04-29 00:17:06 補充:

    試試這個

    http://www.csie.ntnu.edu.tw/~u91029/Prime.html#3

  • 卸貨
    Lv 5
    7 years ago

    請改用 Miller-Rabin 測試法試試看,速度應該會加快不少。

    2014-02-02 19:26:57 補充:

    C 語言程式碼在 C++ 不是都通用嗎?

    2014-02-02 19:36:57 補充:

    提醒您:

    Miller-Rabin 測試通過的東西不一定就是質數,只能代表這個被測數有 ?? 的機率是個質數(但是沒通過測試的一定不是質數)。實際應用時通常會對待測數測個 N 次(每次都使用不同的底數),如果說測一次通過代表有 1/4 機率不是質數的話,那測三次都通過而待測數卻不是質數的機率就只剩下 1/64 了!而通常來說一個數能測個四次八次就很準了。

    當然也有別的演算法可以準確的判定一個數確實是不是質數(方法的名字忘了),只是這個計算比較耗時,實際應用上不如 Miller-Rabin 來的有用。

    2014-02-02 20:18:06 補充:

    stdio.h 和 iostream 基本上是類似的東西,一個是 C 語言的,一個是 C++ 的;當然,在 C++ 裡面使用 stdio.h 是肯定可以的,因為 C++ 相容於 C 語言。

    stdio 的意思就是 Standard Input and Output,即標準輸入輸出。stdio.h 裡宣告有很多函式,但最長用的大概就是 printf 和 scanf 了!其他的函式可以參考下面網站:

    http://www.cplusplus.com/reference/cstdio/

    2014-02-02 20:19:07 補充:

    printf 的地位類似於 std::cout;而 scanf 的地位類似於 std::cin,至於詳細的用法和 C++ 比起來複雜許多,就不解釋了,真有看不懂的地方再問吧!

    2014-02-03 14:35:22 補充:

    這提我都寫出來了,還是加上大數運算的!

    有興趣的人可以去這邊看看:

    http://www.openfoundry.org/of/projects/2419/websvn

    點選 trunk/igngenlib/ign/bignum/bignum_math.c

    搜尋 miller_rabin_test 這個函式就是了(應該在最下面)

    2014-02-03 23:13:32 補充:

    Leo小老師:

    你拿什麼程式碼去測試?

    怎麼測試的?

    錯誤訊息是什麼?

    如果你是拿我的那個 bignum_math.c 去用的話,基本上這個程式碼參考一下就好,如果你真想編譯執行的話可以:

    1. 用 Subversion 簽出 http://svn.openfoundry.org/igntoolkit/trunk 這個碼庫

    2. 開啟 igngenlib/ign/cipher/rsa_test.cbp 這個 Code::Blocks 的專案檔後編譯執行

    2014-02-03 23:14:25 補充:

    不過這個程式主要目的不是用來檢查質數,而是做 RSA 加密,檢查質數只是當中的一個環節。之所以叫你這樣用是因為如果你要讓那個程式碼不只看而已,還能編譯執行的話,這樣是最簡單的方式。

    2014-02-06 18:08:50 補充:

    要跳過2的倍數還不簡單?根本就不需要花時間檢查,i++ 改成 i+=2 就好。

Still have questions? Get your answers by asking now.