求質數的演算法
根據素數的性質，代碼設計如下：
設計一：判斷n是否能被1~n-1整除，不能整除為素數
#include<stdio.h>
int main()
{
int i, n;
scanf("%d", &n);
for (i = 2; i < n ; i++)
{
if (n%i == 0)
break;
}
if (i < n) printf("This is not a prime.");
else printf("This is a prime.");
return 0;
}
設計二：判斷n是否能被2~√n間的整數整除，不能整除為素數
#include<stdio.h>
#include<math.h>
int main()
{
int n,i;
double k;
scanf("%d", &n);
k = sqrt(n);
for (i = 2; i <= k;i++)
{
if (n%i == 0) break;
}
if (i <=k) printf("This is not a prime.");
else printf("This is a prime");
return 0;
}
(1)求質數的演算法擴展閱讀：
1.素數的定義是只能被1和他本身整除,1不是素數.因此要判斷一個數是否為素數.就要判斷它能不能被比他小的所有素數整除,這是一個演算法.(寫到演算法時,我只能寫出用它除以比他小的所有數,造成運算速度低下)
2.如果一個質數大於根號n，而n可以除盡它，那麼n必然也可以除盡一個更小的質數。由此可以得到一個法2較快的素數判斷演算法
『貳』 math：求質數的幾種演算法
你想想吧，如果判斷100是否為素數，那就是用2、3、4……去除100，只要有一個被整除了，那100就不是素數！sqrt(100)是求100的平方根的意思，100的平方根是10，用2、3、4……10去除100就可以了，用不著再用11、12、13……99去除100了。為什麼呢？因為一個數是它的兩個平方根之積，用其中一個平方根之內的各個數遍歷了，難道還有漏網的數未去除「這個數」？比如100吧，找個大於其平方根10的好說的數20為例，說沒有必要用20去除100了就是因為你已經用5除過了，100不是素數！a÷b=c的話，那a÷c不就等於b嘛，幹嘛非得反過來再除一次？這樣做的目的是為了提高代碼時效，試想10000的平方根是100，用這方法10000是不是素數頂多做100次除法就知道了，不然就可能要做9999次，哪個時效高？多說一句，從判定「是不是素數」這一點上說，有沒有sqrt(這個數)倒確實是無意義的……
『叄』 如何算出一個數的所有質數
1、找到這個數字的平方根m=√m
2、找到不大於m的所有質數。
3、在一張自然數表上劃掉所有質數的整數倍（質數本身不劃掉）
4、把1劃掉。
5、沒有劃掉的數字就是質數。
例如，我們要找到100以內的所有質數，只需要按照下面的步驟進行：
1、計算100的平方根，是10。
2、10以內的質數有2、3、5、7
3、劃掉2、3、5、7的整數倍。首先劃掉2的倍數，如4、6、8…、98、100，然後劃掉3的倍數，如6、9、12、15、…、99， 重復的就不需要再劃掉了。然後劃掉5的倍數，7的倍數。
4、最後劃掉1。
(3)求質數的演算法擴展閱讀
質數與黎曼猜想
我們之前談到：質數與黎曼猜想之間有著千絲萬縷的聯系。1896年，法國科學院舉行比賽：徵稿證明黎曼定理。兩位年輕的數學家阿達馬和德·拉·瓦萊布桑獲得了這一殊榮。
實際上這兩位數學家並沒有證明黎曼猜想，只是獲得了一點進展，但是這一點進展就一舉證明了歐拉和勒讓德的猜想，把素數猜想變成了素數定理。黎曼猜想的威力可見一斑。
1901年，瑞典數學家科赫證明：如果黎曼猜想被證實，那麼素數定理中的誤差項c大約是√xln(x)的量級。
即便黎曼猜想被證實，人們也只是在質數規律探索的過程中更近了一步，距離真正破解質數的規律，還有很長的路要走。也許質數就是宇宙留給人類的密碼。
『肆』 求質數方法
篩法求質數：
用篩法求質數的基本思想是：把從1開始的、某一范圍內的正整數從小到大順序排列， 1不是質數，首先把它篩掉。剩下的數中選擇最小的數是質數，然後去掉它的倍數。依次類推，直到篩子為空時結束。如有：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是質數，去掉。剩下的數中2最小，是質數，去掉2的倍數，餘下的數是：
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的數中3最小，是質數，去掉3的倍數，如此下去直到所有的數都被篩完，求出的質數為：
2 3 5 7 11 13 17 19 23 29
(4)求質數的演算法擴展閱讀：
質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中，將會因為找質數的過程過久，使即使取得信息也會無意義。
在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。。
參考資料：
網路--篩法求素數
『伍』 找出1－100之間的質數，該怎麼設計演算法
100以內的質數共有25個，這些質數我們經常用到，可以用下面的兩種辦法記住它們。
� 一、規律記憶法
� 首先記住2和3，而2和3兩個質數的乘積為6。100以內的質數，一般都在6的倍數前、後的位置上。如5、7、11、13、19、23、29、31、 37、41、43……只有25、35、49、55、65、77、85、91、95這幾個6的倍數前後位置上的數不是質數，而這幾個數都是5或7的倍數。由此可知：100以內6的倍數前、後位置上的兩個數，只要不是5或7的倍數，就一定是質數。根據這個特點可以記住100以內的質數。
� 二、分類記憶法
� 我們可以把100以內的質數分為五類記憶。
�第一類：20以內的質數，共8個：2、3、5、7、11、13、17、19。
�第二類：個位數字是3或9，十位數字相差3的質數，共6個：23、29、53、59、83、89。
�第三類：個位數字是1或7，十位數字相差3的質數，共4個：31、37、61、67。
�第四類：個位數字是1、3或7，十位數字相差3的質數，共5個：41、43、47、71、73。
�第五類：還有2個持數是79和97。
� 一種簡便的試商方法
� 試商是計算除數是三位數除法的關鍵，當除數接近整百數時，可以用「四捨五入法」來試商，然而當除數十位上是4、5、6不接近整百數時，試商就比較困難，有時需要多次調商。為了幫助同學們解決這個困難，下面介紹一種簡便的試商方法。
� 當除數十位上是4時，捨去尾數看做整百數。用整百數做除數得出的商減1後去試商。
� 命名如1944÷243，除數十位上是4，把243看做200，1944÷200商9，用8(9－1)去試商正合適。
� 當除數十位上是5、6時，捨去尾數向百位進1，把除數看做整百數，用整百數做除數得出的商加1後去試商。
� 例如：1524÷254除數十位上是5，把254看做300，1524÷300商5，用6(5＋1)去試商正合適。
� 運用上面這種試商方法，有的可以直接得出准確商，有的只需調商一次就行了。同學們不試在計算除法時試一試。
c++:輸出1~100的質數
#include<iostream>
using namespace std;
int main()
{
int i, j;
for(i=1;i<=100;i++) {
for(j=2;j<i;j++)
if(i!=j&&i%j==0)
break;
if(i == j) cout<<i<<endl;
}
system("pause");
}
『陸』 求質數的最優演算法
#include <stdio.h>
int main()
{ int i,j,t;
for (i=2;i<100;i++)
{ t=1;
for (j=2;j<i;j++) /找因數的范圍可以是2到一半 或者平方根，甚至 可以 比平方根小的質數，當然要建一個數組
if (i % j ==0)
{ t=0;
break;
}
if (t==1)
printf("%d\n",i);
}
return 0;
}
『柒』 c語言求質數的演算法，講方法也行，不要那種on2的演算法
【小學生版】
判斷 x 是否為質數，就從 2 一直算到 x-1。
【小學生畢業版】
稍微聰明一點的：x 如果有質因數，肯定會小於等於 x/2，所以捏，就從 2 一直到 x/2 即可。
這一下子就少了一半的工作量哦。
【初學生版】
再稍微聰明一點：除了2以外的質因數都是奇數。所以算從3開始一直到 x/2 的所有奇數。
這一下子，工作量又少了一半哦。
【高中生版】
再聰明的發現：其實只要從 2 一直嘗試到【根號x】，就可以了。因為x只要有因數必定有一個因數小於等於根號x。
【本科生版】
機智的本科生：要是把初中學生+高中生=只要判斷2到根號x之間的奇數⊙▽⊙
【本科畢業生版】
稍加機智的發現：其實，只要嘗試小於根號x 的質數即可。而這些質數，恰好前面已經算出來了。於是會把已經算出的質數，先保存起來，然後用於後續的判斷，效率就大大提高了。【空間換時間】
【之後的版本】我還沒本科畢業⊙▽⊙。。。
『捌』 python求質數的演算法
很早 的一個 函數
『玖』 求 質數 的計算公式
質數公式
當N為正整數時，形如 （N！）N+1的數一定是質數
不信大家去驗證看看！
在公式A=(n-1)*(¦¦B2-1¦-(B2-1)¦)/2+2, 其中B=m(n+1)-(n!+1)中，m,n以自然數代入，所得的結果一定是素數。 這就是自歐幾里德在<<幾何原本>>證明了素數是無限多個後，多少世紀以來人們一直所尋找的能寫出所有素數的公式! 不難看出，A一定是整數，且有: 若B=0,有A＝n+1; 若B≠0, 有A=2. B≠0時，A已為素數，當B=0, 即m(n+1)-(n!+1)=0, 即m=(n!+1)/(n+1).在初等數論中有一著名的定理叫做"威爾遜定理", 可陳述為(n!+1)/(n+1)為整數的充要條件是n+1是素數。所以B=0時，m=(n!+1)/(n+1)為整數，故A＝n+1必為素數。
或嘗試下面公式：
X取任意正整數,如對於下式ab沒有正整數解時.6X+1或6X-1必為素數!(本式可給出所有素數,當1、2式無解時，6X+1為素數，當3、4時無解時，6X-1為素數，當X在1-4式均無解時，則6X+1、6X-1均為素數，同時也證明了孿生素數有無窮多的猜想成立，相反，凡X有解時，則上述均非素數)
(1)6ab+a+b=x
(2)6ab-a-b=x
(3)6ab+a-b=x
(4)6ab-a+b=x
『拾』 求 質數 的計算公式
摘要 P=(r1+1)×(r2+1)×(r3+1)×……×(rn+1)