素數判定演算法

❶ 判斷一個整數是不是素數的演算法

建立一個素數表（一般不大於此整數的算術平方根即可）進行試除，或者利用一些常見素數性質，以及被素數整除的性質來判斷

❷ 判斷一個數是否是素數

判斷是否是質數最直觀和簡單的方法就是從2開始直接除，能除盡（余數為0）就不是質數。則C語言實現為：
int isprime(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0）
return 0;
else
return 1;
}
該演算法的時間復雜度O(n)。
可以改進一下，根據如果一個數是合數，那麼它的最小質因數肯定小於等於它的平方根。用反證法可以證明一下。假設x是n的最小質因數，則存在n/x=p。p>x,x*p=n。如果x不小於等於它的平方根，則x*x>n,而p>x，故x*p>n,假設不成立。合數是與質數相對應的自然數。一個大於1的自然數如果它不是合數，則它是質數。也就是說如果一個數能被它的最小質因數整除的話，那它肯定是合數，即不是質數。所以判斷一個數是否是質數，只需判斷它是否能被小於它開跟號後的所有數整除，因此，這樣做的運算少了很多，降低了時間復雜度。

❸ c語言如何判斷素數

素數又稱質數，所謂素數是指除了 1 和它本身以外，不能被任何整數整除的數，例如17就是素數，因為它不能被 2~16 的任一整數整除。判斷一個整數m是否是素數，只需把 m 被 2 ~ m-1 之間的每一個整數去除，如果都不能被整除，那麼 m 就是一個素數。

首先要知道素數是不等於1，它的因子只有1和它本身。判斷一個數是否為素數，可以用大於1小於給定數的所有數去除給定數，如果有任何一個能夠除盡，就表示是合數，反之是素數。

(3)素數判定演算法擴展閱讀：

首先，本文英文字母都表示整數，上半部B 》3N 》W，下半部B 》W 》3N。大於3的素數只有6N-1和6N+1兩種形式，我們只需判定這兩種數是素數還是合數即可。

命題 1 對於B=36N+1 形數而言。

若不定方程（3N）^2+N-（B-1）/36=W^2 有整數解，

則 6（3N-W）+1 是小因子數；6（3N+W）+1 是大因子數。

若不定方程 （3N）^2-N-（B-1）/36=W^2 有整數解，

則 6（3N-W）-1 是小因子數；6（3N+W）-1 是大因子數。

兩式都無解，是素數。

❹ 判斷一個數是否是素數的最簡便演算法

滿足是素數的最低要求是滿足小費馬定理，即素數定理。
但是滿足小費馬定理，不一定就是素數。

❺ 判斷一個數a是否為素數的演算法。

int prime(int n)
{int i;
for (i=2;i<=sqrt(n);i++)
if(n%i==0)
return 0;
return 1;
}
若返回0則不是素數；
若返回1則是素數

❻ c語言求素數的演算法

根據素數的性質，代碼設計如下：

設計一：判斷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;

}

(6)素數判定演算法擴展閱讀：

1.素數的定義是只能被1和他本身整除,1不是素數.因此要判斷一個數是否為素數.就要判斷它能不能被比他小的所有素數整除,這是一個演算法.(寫到演算法時,我只能寫出用它除以比他小的所有數,造成運算速度低下)

2.如果一個質數大於根號n，而n可以除盡它，那麼n必然也可以除盡一個更小的質數。由此可以得到一個法2較快的素數判斷演算法

❼ 文字敘述判斷一個數是否為素數的基本演算法

素數是一個大於1，除了1和自身外沒有其他因子的自然數。
假設要判斷的數為a
（1）若a<=0 ,則提示錯誤，或直接認為不是素數
（2）若a==1 不是素數。
（3）若a>1 則讓a除以 2到a-1的數，如果有一個整出，則a不是素數，若都不能整除，則表示
a只有1和a兩個因子，則a是素數。

❽ 什麼是素數呀,判斷是不是素數的演算法是什麼呀

素數只能被自身或1整除。