新手求教 c語言素數判斷演算法,用C語言如何判斷素數?

時間 2021-12-20 15:36:58

1樓:匿名使用者

就是判斷從2開始到乙個數的平方根中若不能被他整除,那麼該數就是素數;

網上**是若能整除則跳出,所有條件不能整除則輸出是素數。

他是只需要一種判斷,不滿足則跳出,那麼跳出後i < n,所以可以用。

你的**思路沒有錯,只不過網上沒有使用的優化的演算法,如果你想弄明白怎麼優化,那你需要在數學中找答案

2樓:獅子

網上的**意思是:n就是你輸入的任意數,判斷它是否是素數的方法是用大於2小於n的數去除n,若能整除即不是素數,跳出迴圈;若數一直增加到n+1都沒有被整除,即可輸出「素數」。

你的源程式:3是素數,很簡單,所以用if來提醒輸入大於3的數,你的只是另一種素數演算法,是優化的演算法,更快。因為只需用2到根號a去判斷。

3樓:去塵遠

第乙個if:如果輸入的數n,能夠整除小於n的某乙個數i,證明數n有約數i,此時break後,i的值一定是小於n的。

第二個if:如果i的值比n大,說明上述的for迴圈沒有進入到第乙個if裡面,所以從2到n-1之間沒有乙個數是n的約數。所以可以判定n是素數。

4樓:湛藍星空

//判斷乙個數num是否為素數

#include

int main()

int num,i,n=0;

while(1)

scanf("%d",&num);//輸入乙個數numif(num==2) printf("%d是素數\n",num);

else if(num>=3)

for(i=1;i<=num;i++)

if((num%i)==0) n++;

if(n==2) printf("%d是素數\n",num);

else printf("%d不是素數\n",num);

n=0;

else printf("%d不是素數\n",num);

return 0;

用c語言如何判斷素數?

5樓:喜歡種蘑菇

素數又稱質數,所謂素數是指除了 1 和它本身以外,不能被任何整數整除的數,例如17就是素數,因為它不能被 2~16 的任一整數整除。

思路1、判斷乙個整數m是否是素數,只需把 m 被 2 ~ m-1 之間的每乙個整數去除,如果都不能被整除,那麼 m 就是乙個素數。

思路2、判斷方法還可以簡化。

m 不必被2~m-1之間的每乙個整數去除,只需被2~√m之間的每乙個整數去除就可以了。如果 m 不能被2~√m 間任一整數整除,m必定是素數。例如判別17是是否為素數,只需使17被2~4之間的每乙個整數去除,由於都不能整除,可以判定17是素數。

原因:因為如果m能被2~m-1之間任一整數整除,其二個因子必定有乙個小於或等於√m,另乙個大於或等於√m。

例如16能被2、4、8整除,16=2*8,2小於 4,8大於4,16=4*4,4=√16,因此只需判定在2~4之間有無因子即可。

兩種思路的**請看解析。

拓展資料:

素數(prime number)又稱質數,有無限個。素數定義為在大於1的自然數中,除了1和它本身以外不再有其他因數。

c語言是一門面向過程、抽象化的通用程式語言,廣泛應用於底層開發。c語言能以簡易的方式編譯、處理低階儲存器。c語言是僅產生少量的機器語言以及不需要任何執行環境支援便能執行的高效率程式語言。

6樓:五四公社

介紹三種使用c語言來判斷素數的方法,以及用做素數表來判斷找素數的方法。

7樓:閾庣憸鈾

從鍵盤上輸入任意乙個整數,然後判斷該數是否為素數。

如果是素數則輸出」this is a prime.」

否則輸出「this is not a prime.」

方法一:判斷n是否能被2~n-1間的整數除方法二:判斷n是否能被2~√n間的整數除

c語言中——三種方法判斷是偶數還是奇數

開頭**:

#include

int main(int argc, const char * ar**)

else

方法二:三目運算子

a%2?printf("奇數!\n"):printf("偶數!\n");

方法三:位與&

if (a&1)

else

8樓:匿名使用者

#include

#include

using namespace std;

int main()

for(int i=2;i

return 0;}

求c語言中 判斷素數的 **!!!!!

9樓:東冬冬冬冬冬

基本思想:把m作為被除數,將2—int( )作為除數,如果都除不盡,m就是素數,否則就不是。

可用以下程式段實現:

void main()

}}2、

說明:解決這個問題的訣竅是如何安排刪除的次序,使得每乙個非質數都只被刪除一次。 中學時學過乙個因式分解定理,他說任何乙個非質(合)數都可以分解成質數的連乘積。

例如,16=2^4,18=2 * 3^2,691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小質數寫在最左邊,有16=2^4,18=2*9,691488=2^5 * 21609,;

換句話說,把合數n寫成n=p^k * q,此時q當然是大於p的,因為p是因式分解中最小的質數。由於因式分解的唯一性,任何乙個合數n,寫成n=p^k * q;的方式也是唯一的。

由於q>=p的關係,因此在刪除非質數時,如果已知p是質數,可以先刪除p^2,p^3,p^4,... ,再刪除pq,p^2*q,p^3*q,...,(q是比p大而沒有被刪除的數),一直到pq>n為止。

因為每個非質數都只被刪除一次,可想而知,這個程式的速度一定相當快。依據gries與misra的文章,線性的時間,也就是與n成正比的時間就足夠了(此時要找出2n的質數)。

**如下:

#include

#include

using namespace std;

int main()

int n; cin>>n;

int *location=new int[n+1];

for(int i=0;i!=n+1;++i)

location[i]=i;

location[1]=0; //篩除部分

int p,q,end;

end=sqrt((double)n)+1;

for(p=2;p!=end;++p)

if(location[p])

for(q=p;p*q<=n;++q)

for(int k=p*q;k<=n;k*=p)

location[k]=0;

int m=0;

for(int i=1;i!=n+1;++i)

if(location[i]!=0)

cout<++m;

if(m%10==0) cout

該**在visual studio 2010 環境下測試通過。

以上兩種演算法在小資料下速度幾乎相同。

10樓:的和有關法規

方法有2個:

1、判斷n是否能被2~√n間的整數整除

#include

#include

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;

2、判斷n是否能被2~n-1整除

#include

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;

擴充套件資料:

c語言的模組化程式結構用函式來實現,即將複雜的c程式分為若干模組,每個模組都編寫成乙個c函式,然後通過主函式呼叫函式及函式呼叫函式來實現一大型問題的c程式編寫,因此常說:c程式=主函式+子函式。因此,對函式的定義、呼叫、值的返回等中要尤其注重理解和應用,並通過上機除錯加以鞏固。

判斷語句(選擇結構):

if 語句:「如果」語句;if—else 語句:「若…(則)…否則…」語句;switch 語句:「切換」語句;switch—case:「切換—情況」語句。

迴圈語句(迴圈結構):

while 語句:「當…」語句;do—while 語句:「做…當…(時候)」語句;for 語句:條件語句(即「(做)…為了…」語句)。

跳轉語句(迴圈結構:是否迴圈):

goto 語句:「轉舵」語句,也稱「跳轉」語句;break 語句:「中斷」(迴圈)語句,即結束整個迴圈;continue 語句:

「繼續」語句(結束本次迴圈,繼續下一次迴圈);return 語句:「返回」語句。

需要說明的是:

1、乙個c語言源程式可以由乙個或多個原始檔組成。

2、每個原始檔可由乙個或多個函式組成。

3、乙個源程式不論由多少個檔案組成,都有乙個且只能有乙個main函式,即主函式。是整個程式的入口。

4、源程式中可以有預處理命令(包括include 命令,ifdef、ifndef命令、define命令),預處理命令通常應放在原始檔或源程式的最前面。

5、每乙個說明,每乙個語句都必須以分號結尾。但預處理命令,函式頭和花括號「}」之後不能加分號。(結構體、聯合體、列舉型的宣告的「}」後要加「 ;」。)

6、識別符號,關鍵字之間必須至少加乙個空格以示間隔。若已有明顯的間隔符,也可不再加空格來間隔。

書寫規則

1、乙個說明或乙個語句佔一行。

2、用{} 括起來的部分,通常表示了程式的某一層次結構。{}一般與該結構語句的第乙個字母對齊,並單獨佔一行。

3、低一層次的語句或說明可比高一層次的語句或說明縮排若干格後書寫。以便看起來更加清晰,增加程式的可讀性。在程式設計時應力求遵循這些規則,以養成良好的程式設計風格。

11樓:摩羯面對現實

c語言中判斷素數的**如下:

#include

int is_prime(int n)

int i;

if(n<=1)

return 0;

for(i=2;i*i<=n;i++)

if(n%i==0)

return 0;

return 1;

int main()

int i,n=0,t=1;

printf("1000以內的素數排列:\n");

for(i=2;i<1000;i++)

if(is_prime(i))

n++;

t++;

printf("%4d",i);

if(t>10)

printf("\n");

t=1;

printf("\n1000以內的素數共有%d個\n",n);

return 0;

擴充套件資料:

c語言中判斷素數的其他**:

#include

int main(void)

unsigned long num;

unsigned long div;

int isprime;

printf("please enter an integer for analysis. ");

printf("enter q to quit.\n");

for(div = 2, isprime = 1;(div * div) <= num; div++)

if(num % div == 0)

if((div * div) != num)

printf("%lu is divisible by %lu and %lu.\n", num, div, num / div);

else

printf("%lu is divisible by %lu.\n", num, div);

isprime = 0;

if(isprime == 1){

printf("%lu 是素數.\n", num);

printf("please enter another integer for analysis. ");

printf("enter q to quit.\n");

printf("bye.\n");

return 0;

c語言求素數,c語言求素數的演算法

例 判斷m是否素數。n s流程圖 include main 例 求100至200間的全部素數。include main if n 5 0 printf printf 我只說思路,就不寫 了,太麻煩。偷懶 定義乙個變數i,從2開始,到你要求的範圍最大數比如說100為止,定義另乙個變數,j,從2開始,到...

用c語言求素數

我不知道如果m是素數的話算不算是第乙個,我這邊算是第乙個的 如果有疑問可以再提問的哦 include stdio.h int isprime int n int main int argc,char const ar if j n printf 數 d的第 d的素數是 d!n m,n,i retur...

c語言如何判斷素數?用c 判斷乙個數是否是素數?

素數又稱質數,所謂素數是指除了 1 和它本身以外,不能被任何整數整除的數,例如17就是素數,因為它不能被 2 16 的任一整數整除。判斷乙個整數m是否是素數,只需把 m 被 2 m 1 之間的每乙個整數去除,如果都不能被整除,那麼 m 就是乙個素數。首先要知道素數是不等於1,它的因子只有1和它本身。...