關於質數的問題

kingplayer620

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

baepi

真不明白現在發帖的主流是不是只要把題目丟出來...像是老師出考題....怪不得這版越來越冷清
離開好久...久久回來一看還是這樣
抱怨到此結束...開始給思路....或許中階以上的高手看不上眼....但這已是我近年來解質數的邏輯
首先...既然指名C語言...那就不是C++...貌似沒有現成的list可以使用吧?...或許...畢竟我只淺游於C++的使用者
假設沒有現成的list可以用....若是新手....則先創建一個很大的 int 陣列...用來存放即將檢測出來的質數...當然若是會 "鏈結串列" 的使用者...那麼就先自行導出一個list出來
...

瀏覽完整內容，請先 註冊 或 登入會員

kingplayer620

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

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

真不明白現在發帖的主流是不是只要把題目丟出來...像是老師出考題....怪不得這版越來越冷清
離開好久...久 ...

感謝大大的分享，我只是剛剛要進入程式界的小菜鳥，未來還有很多要學習的地方，我看到這題的想法是用陣列去寫，但想知道更快運算的方法，所以才發問，哈，算是多方面思考...

瀏覽完整內容，請先 註冊 或 登入會員

羕漾

要找更快的方法可以從數學公式去著手
例如判斷 N 是否為質數，只要判斷根號N以內的數是否是質數就行
再來偶數中只有 2 是質數，所以 i = 3 以後，迴圈可以 i+=2 來跑，因為不用判斷偶數是否是質數
以此類推將一些數學的公式套上去，就可以得到一個較快速的質數解
另外陣列或串列這些資結的則是你該研究的部份，如何讓你的程式可以有效率的跑上面列出來的數學公式，幫助你計算質數！

---

...

瀏覽完整內容，請先 註冊 或 登入會員

z1090128

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

jackyo04

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

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

給定N，我們宣告一個bool[N+1], 初始值都是false(代表質數)(index 0不用)
bool v[N+1]=false;
for(int x=2;x<=N;x++){
    if(v[x]==true) continue;
    for(int y=x*2;y<=N;y+=x){
        v[y]=true;
...

瀏覽完整內容，請先 註冊 或 登入會員

z1090128

先記錄已知的質數，在使用這些質數去拼湊應該會比快