c語言質數判斷

❶ c語言篩選法判斷質數

樓上的別在那誤導人，你那叫篩選法嗎？
先解釋一下篩選法的步驟：
<1>先將1挖掉(因為1不是素數)。
<2>用2去除它後面的各個數，把能被2整除的數挖掉，即把2的倍數挖掉。
<3>用3去除它後面的各數，把3的倍數挖掉。
<4>分別用4、5…各數作為除數去除這些數以後的各數。
上述操作需要一個很大的容器去裝載所有數的集合，只要滿足上述條件，即2的N次方的全部置0，3的N次方的全部置0，4的N次方的全部置0.。。。一直到這個數據集合的末尾，這樣一來不為0的數就是素數了，然後按下標在裡面進行查找就好了
篩選法程序如下
#include<stdio.h>
intmain()
{
intx[100001];
inttemp,n,i;
//初始化數組
for(i=0;i<100001;i++)
x[i]=0;
//初始化數組完成
/*
預計結果，
數組中質數為0，其它為1
*/
x[0]=x[1]=1;//因為0和1不能通過計算得到，所以只能手工置1，1即不是合數也不是質數
for(i=2;i<100001;i++)
{//循環數組中的每個數
if(x[i]==0){//如果該數所存的值為0，即第一次接觸此數
temp=2*i;//將它的二倍，及n倍（要小於100000），都置為1，因為這些數都能被i整除
while(temp<=100000)
{
x[temp]=1;
temp+=i;
}
}
}
scanf("%d",&n);
while(n!=0)
{
if(x[n]==0)
printf("素數
");
else
printf("合數
");
scanf("%d",&n);
}
return0;
}
如果你覺得這個方法不好理解，你可以用上面他們寫的那些常規演算法，但是數字過大的話，算起來是很慢的

❷ c語言編程 判斷一個數是否為質數

錯誤較多，修改如下：

//---------------------------------------------------------------------------
#include <stdio.h>
void main()
{
int a,n;
scanf("%d",&a);
if(a==0||a==1)
printf("no");
else if(a==2) //注意這里
printf("yes");
else
{//注意這里
for(n=2;n<a;n++)
{
if(a%n==0)
{ //注意這里
printf("no");
break; //注意這里
} //注意這里
}
if (n==a)//注意這里
{
printf("YES");
}
}//注意這里
}
//---------------------------------------------------------------------------

❸ C語言編程：判斷某數是否是質數

#include<stdio.h>
#include
<math.h>//包含sqrt函數
int
prime(int
m);
main(){
int
m;
scanf("%d",&m);
if(prime(m))
printf("%d是質數",m);
else
printf("%d不是質數",m);
}
int
prime(int
m){
int
i,n=sqrt(m);
for(i=2;i<=n;i++)
{
if(m%i==0)return
0;//如果整除，終內止循環，容返回0
}
return
1;
}

❹ 用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語言如何判斷素數

按照如下步驟即可用C語言判斷素數：

1、首先打開visual C++ 6.0，然後點擊左上角的文件，再點擊新建。

❻ C語言判斷素數

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
using namespace std;
int prime(int x){
for(int i=2;i<x;i++){
if(x%i==0)
return 0;
}
return 1;
}
int main(){
int a=0; // 素數的個數
int num[9]; // 輸入的整數
int numl[9]={0};
printf("輸入10個整數：\n");
cfu:
//有個小BUG需要輸入11個數，最後一個不算入計算之內。
for(int i = 0;i < 10;i++){
scanf("%d\n",&num[i]);
}
for (int i = 0;i < 10;i++)
{
if (num[i] >= 50 && num[i] <= 2000)
{
//判斷是不是素數；
if(prime(num[i])==1){
printf("%d 不是素數\n",num[i]);
}
else{
printf("%d 是素數\n",num[i]);
numl[a++] = num[i];
}
}else{
printf("請輸入50到2000之間的數\n");
goto cfu;
}
}
//排序寫在這里就可以了。
int lenth = a;
cout << "長度為: "<< lenth << endl;
for (int i = 0;i < lenth-1;i++)
{
for (int j = 0;j < lenth-1-i;j++)
{
if (numl[j] < numl[j+1] )
{
int temps = numl[j];
numl[j] = numl[j+1];
numl[j+1] = temps;
}
}
}
for (int i=0;i<lenth;i++)
{
printf("%d ",numl[i]);
}
while(1);
return 0;
}
//好像看錯題了，我的是輸入10個數判斷是否是素數，，，，，
//這個重新寫了一個，就符合題的意思了,你想輸出其他的素數就自己加條件,當成拓展就可以了.
#include "stdafx.h"
#include <iostream>
using namespace std;
int prime(int x){
for(int i= 2;i< x ; i++){
if(x%i == 0)
return 0;
}
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int m,k=0;
int arr[2000]={0};
printf("輸入50到2000之間的整數: ");
cfu:
scanf("%d",&m);
if (m >= 50 && m <= 2000)
{
//判斷在m以內有素數
for (int i =2;i < m; i++)
{
if (prime(i)==1){
printf("%d 是素數\n",i);
arr[k++]= i;
if (k == 10)
{
break;
}
}else{
printf("%d 不是素數\n",i);

}
}

}else{
printf("輸入50到2000之間的整數");
goto cfu;
}
cout << "K的值： "<< k << endl;
for (int i = 0;i < k-1;i++)
{
for (int j = 0;j < k-1-i;j++)
{
if (arr[j] < arr[j+1] )
{
int temps = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temps;
}
}
}
printf("10個數排序：");
for (int i = 0;i< k; i++)
{
printf("%d ",arr[i]);
}
while(1);
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;

}

(7)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)

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 環境下測試通過。

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