篩法求素數c語言

1. 求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;

}

(1)篩法求素數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 環境下測試通過。

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

2. 篩法求素數c語言詳解

#include <stdio.h>
int main()
{
int x = 0,i = 0;
scanf("%d",x);
for(i = 2;i < x;i++)
{
if(x % i == 0)
{
printf("%d不是素數!\n",x);
}
}
printf("%d是素數!\n",x);
return 0;
}

3. c語言中用篩選法求素數

一個質數。在大於1的自然數中，除1和100整數本身外，不能被任何其他自然數整除的次數。素數在數論中起著重要的作用。

大於1但沒有質數通道的數稱為合數。1和0既不是質數也不是合數。

通過濾波法得到的100以內質數的源代碼如下：

＃include＂stdio．h＂

main（）

main（）

｛

IntI，j。

對於(I = 2;我< 99;我+ +)

｛

對於(j = 2;<我;J + +)

｛

If（I％j＝＝0）

｛

打破；

｝

如果（j＝＝I－1）

｛

Printf（「％4d」，I）；

｝

(3)篩法求素數c語言擴展閱讀：

100以內的數字代碼如下

包含< bits/stdc++。H >

使用命名空間性病。

Intthesum（Intn）

｛

返回（n／10＋n％10％）＋（10）（n／10％＊（n％10））；

｝

Intmain（）｛

Intn＝100；

For (int I = 10;I < = n;我+ +)

｛

If (sum (I) = = I) cout < < I < < endl;

｝

返回0；

｝

4. 篩法求素數的C語言實現

1、演算法一：令A為素數，則A*N（N>1;N為自然數）都不是素數。 #definerange2000boolIsPrime[range+1];//set函數確定i是否為素數，結果儲存在IsPrime[i]中，此函數在DEVC++中測試通過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=4^2，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的質數）。 （摘自《C語言名題精選百則（技巧篇）》，冼鏡光 編著，機械工業出版社，2005年7月第一版第一次印刷）。代碼如下： #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){if(Location[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 環境下測試通過。
以上兩種演算法在小數據下速度幾乎相同。

5. c語言編程 素數篩選

用篩法求100以內的素數：

#include<stdio.h>

int main()

{

int a[101],i,j;

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

a[i]=1;

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

for(j=i+i;j<=100;j+=i)

a[j]=0;

printf("100以內的素數： ");

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

if(a[i])printf("%d ",i);

printf(" ");

getch();

return 0;

}

6. C語言編程:用篩選法求100之內的素數,

源代碼如下：

#include <stdio.h>

#include <math.h>

int main()

{

int a, b, i, flag;

printf("輸入兩個整數: ");

scanf("%d %d", &a, &b);

printf("%d與%d之間的素數為: ", a, b);

while(a<b)

{

flag=0;

for(i=2; i<=sqrt(a); i++)

{

if(a%i==0)

{

flag=1;

break;

}

}

if(flag==0)

printf("%d ", a);

a++;

}

return 0;

}

(6)篩法求素數c語言擴展閱讀

一個偶數總能表示為兩個素數之和的源代碼如下：

#include "stdio.h"

#include "math.h"

main()

{

int a,b,c,d;

scanf("%d",&a);

for(b=3;b<=a/2;b+=2)

{

for(c=2;c<=sqrt(b);c++)

if(b%c==0) break;

if(c>sqrt(b))

d=a-b;

else

break;

for(c=2;c<=sqrt(d);c++)

if(d%c==0)

break;

if(c>sqrt(d))

printf("%d=%d+%d ",a,b,d);

}

}

for(int i=5;i<=sqrt(x);i+=6)

if(x%i==0||x%(i+2)==0)

{

printf("%d不是素數",x);

return 0;

}

printf("%d是素數",x);

return 0;

}

7. 篩法求素數...c語言...

給你原理，你就應該明白是怎麼回事了
求素數n，n是否會被2~n之間的數整除，如果不整除，那麼是素數，有一個整除了，就不是素數，這個道理應該明白
那麼就是一個游遍2~n這些數，判斷是否有整除的
但是2~n所判斷的數太多，要縮小范圍
一個數的因子是圍繞根號n兩邊排列的，也就是說，在根號n之前有個數x可以整除n，設x*y=n的話，y一定在根號n到n之間，這個道理也不難驗證
因為xy大小最接近的時候，是x=y，就是x*x=n的話，x就等於根號n。要是xy不相等的話，一個小於根號n，那麼另一個必然大於根號n
所以只判斷2~根號n之間的數就可以，也就是判斷一半。

1~100之間的數據，那麼因子只判斷2~10之間的就可以，要是更精簡一些，值判斷10之前的素數即可，因為8 9 10在2 3 的時候已經為零了

8. C語言 用篩選法求100以內的素數

/*
你之前寫的代碼我不知道是什麼原理，所以我改了一部分

首先，搞清楚素數的原理,再做題吧!

1與本身之間的數（不包括1與本身）,都不能被本身整除，則是素數

例如: 8是否為素數?
判斷方法:用8依次除以(2,3,4,5,6,7)這幾個數，其中只要有一個能被整除(8/2=4,8/4=2,余數為0)
，那麼8就不是素數
*/
#include<stdio.h>
#define NUM 100 //預處理，只要將100改成其他的數，就可以給定值以內的素數
void main()
{
int a[NUM+1];
int b,n;
for(b=1;b<=NUM;b++) {
a[b]=b; //*使a[1]~a[100]值為1~100
}
a[1]=0; //*挖掉a[1]
for(n=2;n<NUM;n++){
for(b=2;b<n;b++){
if(a[n]%b==0){ //判斷a[n]是否能被1與本身之間的數整除,
a[n]=0; //不是素數，賦值為0
break; //跳出第二重循環，繼續判斷下一個數
}
}
}
for(b=1;b<=NUM;b++){
if(a[b]!=0) { //判斷是否非0，是則輸出
printf("%5d",a[b]);
}

}
}

9. C語言篩法求100以內的素數

#include<stdio.h>
int main()
{
int i,j;//定義兩個變數，i是從2到100的數字，j是用來被i除，檢驗i是否是素數的數
for(i=2;i<=100;i++)//i從2到100，挨個枚舉，用下面的演算法檢驗
{
for(j=2;j<i;j++)//j從2到i-1，用i除以j
{
if(i%j==0)//如果i除以j的余數是0，即i不是素數
{
break;//跳出循環
}
if(j==i-1)//如果直到j=i-1時上面的判斷一直沒成立，即i不是素數，輸出i
{
printf("%d ",i);
}
}
}
return 0;
}
這是我能寫出來的最簡單的演算法沒用數組，函數什麼的，你應該能看懂
打字不易，如滿意，望採納。