查看完整版本: 關於質數的問題
頁: [1]

kingplayer620 發表於 2017-12-12 10:34 PM

關於質數的問題

隨便輸入一個整數,把這個數前面的所有質數相加。要求:用C語言寫,且輸入的數值很大時,運算跑的速度要快。

<div></div>

baepi 發表於 2017-12-13 12:33 AM

真不明白現在發帖的主流是不是只要把題目丟出來...像是老師出考題....怪不得這版越來越冷清
離開好久...久久回來一看還是這樣
抱怨到此結束...開始給思路....或許中階以上的高手看不上眼....但這已是我近年來解質數的邏輯
首先...既然指名C語言...那就不是C++...貌似沒有現成的list可以使用吧?...或許...畢竟我只淺游於C++的使用者
假設沒有現成的list可以用....若是新手....則先創建一個很大的 int 陣列...用來存放即將檢測出來的質數...當然若是會 "鏈結串列" 的使用者...那麼就先自行導出一個list出來
之後只要一個for迴圈從2開始跑到使用者輸入的數值...並從中檢測已知的質數相除是否為0...就不用每次都從2跑到該值了...範例如下(新手版)int ans;
        int ans_index = 0;
        for(int i = 2 ;i <= user_input ; i++)
        {
                bool check = true;
                for(int j = 0 ; j < ans_index ;j++)
                {
                        if((i % ans) == 0)
                        {
                                check = false;
                                break;
                        }
                }
                if(check)
                {
                        ans = i;
                        ans_index++;
                }
        }
        for(int i = 0 ; i < ans_index;i++)
        {
                //自己去加吧
        }歡迎其他大神給出更有效率的解法{:47:}

...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

kingplayer620 發表於 2017-12-16 10:28 PM

baepi 發表於 2017-12-13 12:33 AM static/image/common/back.gif
真不明白現在發帖的主流是不是只要把題目丟出來...像是老師出考題....怪不得這版越來越冷清
離開好久...久 ...

感謝大大的分享,我只是剛剛要進入程式界的小菜鳥,未來還有很多要學習的地方,我看到這題的想法是用陣列去寫,但想知道更快運算的方法,所以才發問,哈,算是多方面思考...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

羕漾 發表於 2017-12-17 03:35 AM

本帖最後由 羕漾 於 2017-12-17 03:48 AM 編輯

要找更快的方法可以從數學公式去著手
例如判斷 N 是否為質數,只要判斷根號N以內的數是否是質數就行
再來偶數中只有 2 是質數,所以 i = 3 以後,迴圈可以 i+=2 來跑,因為不用判斷偶數是否是質數
以此類推將一些數學的公式套上去,就可以得到一個較快速的質數解
另外陣列或串列這些資結的則是你該研究的部份,如何讓你的程式可以有效率的跑上面列出來的數學公式,幫助你計算質數!相關的數學公式你可以找找 Eratosthenes
另外依上面的想法寫出來的程式還不一定是最快的,在一些資料結構上可以動手腳,但這塊我覺得你可以自己研究看看
自己努力找到的東西,自己的印象才會深刻!



...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

z1090128 發表於 2018-5-2 10:39 PM

可以先建立database來讓你有幾個可以記數的條件,再慢慢加上去,不然就是找有沒有比較好的演算法<br><br><br><br><br><div></div>

jackyo04 發表於 2018-6-21 09:34 AM

找更快?看你工具會不會用,知道的工具多不多而已,每個人了解的工具都不一樣,你不把你用的東西PO出來,就要看別人的,這樣很難做討論{:52:}

love88131496 發表於 2018-7-13 09:29 PM

找質數的方法,樓上都討論過,不贅述。
但這題目有意思,是N之前所有質數合,所以意思是,要找出每一個質數。所以個人解釋一個簡單的算法,但不確定是否有用:

給定N,我們宣告一個bool, 初始值都是false(代表質數)(index 0不用)
bool v=false;
for(int x=2;x<=N;x++){
    if(v==true) continue;
    for(int y=x*2;y<=N;y+=x){
        v=true;
    }
}
//跑完以後,應該v[?]=false都是質數,所以
int sums=0;
for(int i=1;i<=N;i++) if(v==false) sums+=i;
std::cout<<sums<<std::endl;

試推算:
        1   2   3   4   5   6   7   8   9   10   11   12  13  14  15  16  17  18  19  20
初始  x   x   x    x   x   x   x   x   x     x     x     x    x    x    x    x    x    x    x    x
x=2  x   x   x    o   x   o   x   o   x     o     x     o    x    o    x    o    x    o    x    o
x=3  x   x   x    o   x   o   x   o   o     o     x     o    x    o    o    o    x    o    x    o
x=4  contunue, 同上   
x=5  x   x   x    o   x   o   x   o   o     o     x     o    ..............
x=6
x=7
x=8
......

可能x不用跑到N, 只要到N/2或是power(N,0.5)就好,沒空去細想...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

z1090128 發表於 2018-12-7 08:44 PM

先記錄已知的質數,在使用這些質數去拼湊應該會比快
頁: [1]