Re: [問題]1到10000之間求質數的程式如何寫?

[BETNPP (NPP)]

※ 引述《iwantnasa (紅髮傑克)》之銘言：
: 我想知道1~10000之間的質數用C++如何找
: 老師建議用輾轉相除法
: BUT我一點頭緒都沒有
: 目前只會FOR回 圈和DO-while
: 不會副程式
: 各位能用簡單的程式教教我嗎?

#include <stdio.h>
int main(){
    //-- 先設一個很大的陣列用來放質數
      int p[10000];
    //--在宣告一個int變數來記錄已經放了多少個質數
      int n=2;
    //--宣告迴圈所需的index
      int num,i;
    //--宣告一個state記錄是否為PRIME
      int prime;
    //--然後先把2跟3放入
      p[0]=2; p[1]=3;
    //--根據質數的定義除了1跟自己以外沒有其他的因數
    //  ＝>不會被小於自己的質數整除
    //用迴圈來控制此條件
      for(num=4;num<10000;num++){      //小於10000的數中依序取一數num
          for(prime=1,i=0;i<n;i++){    //在比num小已知的prime number數列中
              if( num%p[i] == 0){      //如果取餘數為零（整除）
                  prime=0;             //則不為質數
                  break;
              }
          }
          if(prime == 1){     //如果在比num小已知的prime number數列中都不能整除
              p[n++]=num;     //則num為餘數，n個數+1
          }
      }
      for(i=0;i<n;i++)
          fprintf(stdout,"%5d",p[i]);
      return 0;
}

ps. 這只是我想到的一種方法而已，當然也可以不要儲存利用GCD來求.....
    例如，一個數n為質數 => GCD(n,i)=1,for all 1＜i≦√n   i為整數
    很多解法......都可以達到同樣效果～多練習看看囉～

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.121.213.202
推 revivalworld:建議把 sqrt() 用進去, 還有迴圈的 num++改成 num+=2
→ revivalworld:這個演算法似乎太暴力了點- -"
推 revivalworld:再給一個建議, 聽過質數的規謬證明吧
→ revivalworld:你可以把已知的質數乘起來 然後+1 就是一個新的質數
→ revivalworld:當然要從最小的2開始乘，中間不可漏掉任何質數
→ revivalworld:嗯...是"歸謬"
→ revivalworld:話說質數證明好像跟這篇沒太大關係...不要理我Orz
推 ledia:全乘起來+1 還是質數是錯的 2*3*5*7*11*13+1 = 59*509
→ ledia:不要誤導別人....
推 ledia:你可能搞不清楚歸謬的本質
→ compbell:樓上是對的，上述証法有假設"質數為有限個"，然後得矛盾
→ compbell:但可沒說已知的質數乘起來+1會是質數
推 xcycl:冼鏡光《C名題精選百則》有很詳盡的討論 @@
→ xcycl:不過才一萬個, 暴力法也是瞬間解吧 XD
推 revivalworld:對不起...我搞錯了
推 revivalworld:謝謝您指出來
推 revivalworld:再推一次表示歉意
推 iwantnasa:能用輾轉嗎?
推 slalala:可輾轉喔~更快~~如果現在的CPU跟RAM很小很慢 暴力法會?!XD
推 BETNPP:嗯....用+=2的確會快近兩倍，不過我只是單純的用數學的判斷
→ BETNPP:慢慢的推而已，我想應該有更好更快的演算法.....
※ 編輯: BETNPP          來自: 220.133.102.247      (04/09 15:18)