c語言求素數代碼
㈠ 用c語言編寫求質數的程序
//我分別寫出了求素數和判斷素數的程序
/*
//判斷一個數是否為素數
#include<stdio.h>
#include<math.h>
int isprime(int);
void main()
{
int inumber;
printf("請輸入一個非負整數: ");
scanf("%d",&inumber);
if(isprime(inumber))
printf("%d是素數!\n",inumber);
else
printf("%d不是素數!\n",inumber);
}
int isprime(int a)
{
int i;
for(i=2;i<=sqrt(a);i++)
if(a%i==0)
return 0;
return 1;
}
*/
/*****************************************************/
//求某個正整數以內的素數
#include"stdio.h"
#include"math.h"
int main(void)
{
int count,i,m,n,num;
printf("請輸入所求范圍(正整數): ");
scanf("%d",&num);
count=0;//count記錄素數的個數
printf("%d以內的素數為:\n",num);
for(m=2;m<=num;m++)
{
n=sqrt(m);
for(i=2;i<=n;i++)
{
if(m%i==0)
break;
}
if(i>n)//如果m是素數
{
printf("%6d",m);
count++;
if(count%10==0)//count為10的倍數時換行
printf("\n");
}
}
printf("\n");
return 0;
}
㈡ 求C語言中 判斷素數的 代碼!!!!!
基本思想:把m作為被除數,將2—INT( )作為除數,如果都除不盡,m就是素數,否則就不是。
可用以下程序段實現:
void main()
{ int m,i,k;
printf("please input a number: ");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) break;
if(i>=k)
printf("該數是素數");
else
printf("該數不是素數");
}
將其寫成一函數,若為素數返回1,不是則返回0
int prime( m%)
{int i,k;
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) return 0;
return 1;
}
(2)c語言求素數代碼擴展閱讀:
篩法求素數
一、基本思想
用篩法求素數的基本思想是:
把從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
二、C++實現
1、演算法一:令A為素數,則A*N(N>1;N為自然數)都不是素數。
#definerange2000
bool
IsPrime[range+1];
/*set函數確定i是否為素數,結果儲存在IsPrime[i]中,此函數在DEV
C++中測試通過*/
voidset(boolIsPrime[])
{
inti,j;
for(i=0;i<=range;++i)
IsPrime[i]=true;
IsPrime[0]=IsPrime[1]=false;
for(i=2;i<=range;++i)
{
if(
IsPrime[i])
{
for(j=2*i;j<=range;j+=i)
IsPrime[j]=false;}}}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<iostream>
#include<cmath>
usingnamespacestd;
intmain()
{
intN;cin>>N;
int*Location=newint[N+1];
for(inti=0;i!=N+1;++i)
Location[i]=i;
Location[1]=0;//篩除部分
intp,q,end;
end=sqrt((double)N)+1;
for(p=2;p!=end;++p)
{
if(Location[p])
{
for(q=p;p*q<=N;++q)
{
for(intk=p*q;k<=N;k*=p)
Location[k]=0;
}
}
}
intm=0;
for(inti=1;i!=N+1;++i)
{
if(Location[i]!=0)
{
cout<<Location[i]<<"";
++m;
}
if(m%10==0)cout<<endl;
}
cout<<endl<<m<<endl;
return0;
}
該代碼在Visual Studio 2010 環境下測試通過。
以上兩種演算法在小數據下速度幾乎相同。
㈢ 求素數的C語言程序!
素數,也叫質數,就是指除了1和該數本身以外,不能被其他任何整數整除的正數。
#include<stdio.h>#include<math.h>voidmain(){intm,k,i,n=0;for(m=1;m<=200;m=m+2){k=sqrt(m);for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1){printf("%5d",m);n=n+1;㈣ C語言求素數代碼
請你把if(r=0)
改為r==0
㈤ 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;
}
(5)c語言求素數代碼擴展閱讀:
1.素數的定義是只能被1和他本身整除,1不是素數.因此要判斷一個數是否為素數.就要判斷它能不能被比他小的所有素數整除,這是一個演算法.(寫到演算法時,我只能寫出用它除以比他小的所有數,造成運算速度低下)
2.如果一個質數大於根號n,而n可以除盡它,那麼n必然也可以除盡一個更小的質數。由此可以得到一個法2較快的素數判斷演算法
㈥ 用C語言如何判斷素數
素數又稱質數,所謂素數是指除了 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語言是僅產生少量的機器語言以及不需要任何運行環境支持便能運行的高效率程序設計語言。
網路——C語言
㈦ c語言求100以內的素數
#include<stdio.h>
//輸出100之內的所有素數
int main()
{
int i;
int j;
int flag = 1;
for(i = 2;i <= 100;i++)
{
for(j = 2;j <= i / 2;j++)
{
if(i % j ==0)
{
flag = 0;
break;
}
}
if(flag == 1)
{
printf("%d ",i);
}
flag = 1;
}
return 0;
}
C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言;
質數(prime number)又稱素數,有無限個。一個大於1的自然數,除了1和它本身外,不能被其他自然數整除。
㈧ 用C語言如何判斷素數
按照如下步驟即可用C語言判斷素數:
1、首先打開visual C++ 6.0,然後點擊左上角的文件,再點擊新建。
㈨ c語言中如何求素數
#include<stdio.h>
#include<math.h>
void main() // 這里不要搞錯了,main
{
int i,n;
printf("輸入一個整數n");
scanf("%d",&n);
n=abs(n);
if(n>2)
{
for(i=2;i<n;i++)// 在for下面跟個if判斷,如果你輸入4的話,這個程序列印兩次4不是
if(n%i==0&&n==i)
scanf("%d是素數",n); break ;// 這里應該是printf了吧,
else
scanf("%d不是素數",n); break;// 這樣會比較好點
}
else
scanf("%d不是素數",n);// 2就不是素數么,
}
這樣也有問題,當你輸入5的時候,for語句先判斷能否整除2,不能整除2的話,就列印不是素數,寫個函數是比較好的方法