伊莉討論區

標題: 關於質數的問題 [打印本頁]
作者: kingplayer620    時間: 2017-12-12 10:34 PM     標題: 關於質數的問題

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

作者: baepi    時間: 2017-12-13 12:33 AM

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

作者: kingplayer620    時間: 2017-12-16 10:28 PM

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

感謝大大的分享，我只是剛剛要進入程式界的小菜鳥，未來還有很多要學習的地方，我看到這題的想法是用陣列去寫，但想知道更快運算的方法，所以才發問，哈，算是多方面思考
作者: 羕漾    時間: 2017-12-17 03:35 AM

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

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



作者: z1090128    時間: 2018-5-2 10:39 PM

可以先建立database來讓你有幾個可以記數的條件，再慢慢加上去，不然就是找有沒有比較好的演算法
作者: jackyo04    時間: 2018-6-21 09:34 AM

找更快？看你工具會不會用，知道的工具多不多而已，每個人了解的工具都不一樣，你不把你用的東西PO出來，就要看別人的，這樣很難做討論
作者: love88131496    時間: 2018-7-13 09:29 PM

提示: 作者被禁止或刪除 內容自動屏蔽
作者: z1090128    時間: 2018-12-7 08:44 PM

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



歡迎光臨 伊莉討論區 (http://a04.eyny.com/) Powered by Discuz!