c語言素數篩選法

1. c語言編程:用篩選法求100之內的素數,要求每隔10行輸出。怎麼寫

#include<stdio.h>
#include<math.h>
#include<string.h>
main()
{
int i,j,tem,n;
for(;;)
{
system("cls");
printf("請輸入要求素數的上限為：\n");
scanf("%d",&n);
printf("2");
for(i=3;i<=n;i+=2)
{
tem=0;
for(j=2;tem==0&&j<sqrt(i);j++)
if(i%j==0)
tem=1;
if(tem==0)
printf(",%d",i);
}
printf("\n");
system("pause");
}
}
//該素數的求法，比第一種無論是在時間復雜度還是空間復雜度上都要簡單的的多
//素數：其實偶數中除了2以外都不是素數，因此只比較奇數即可；當判斷一個數是不是素數時，
//往往不必算是否能被2—n-1中任意一個數整除
//只要比較是否能被2—sqrt（n）中的任意個數整除即可！
//當能被其中之一整除時，即能判斷該數已不是素數，沒有必要再循環判斷了！

//============================================================Mr_computer

2. 篩法求素數的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 環境下測試通過。
以上兩種演算法在小數據下速度幾乎相同。

3. C語言 用篩法求1-1000之間的素數

1、寫我們的頭文件和主函數。寫好我們的開頭。

4. 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;

}

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

}

5. 解釋一下c語言篩選法求素數

如果定義為
a[100]
那麼該數組的下標范圍是：
a[0]
~
a[99]
為了用
a[100]
就不得不定義到101
這句表示執行以下100行代碼：
a[1]=1;
a[2]=2;
a[3]=3;
……
a[100]=100;
用循環語句寫就是：
for(i=0;i<101;i++)
a[i]=i;
每當輸出到第10個，20個……
90個
的時候就換行
而10，20
……
90
這些數有一個共同特徵：
他們
%
10
==0
所以可以這樣：
for
(i=1
;
i<101
;
i++)
{
printf("%d
",a[i]);
if
(i%10==0)
printf("\n");
}
*********************************
a[i]不是一個變數
當i分別取1，2，3……，100
的時候
a[i]表示的是a[1],a[2],a[3],……a[100]
這100個變數

6. 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>
int
main()
{
int
x[100001];
int
temp,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("素數\n");
else
printf("合數\n");
scanf("%d",&n);
}
return
0;
}
如果你覺得這個方法不好理解，你可以用上面他們寫的那些常規演算法，但是數字過大的話，算起來是很慢的

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

先建立一個數組賦值為2-100

再用二重循環標記每個素數的倍數為0，最後列印出為被標記不為0的數即為素數

#include"stdio.h"

#defineSize99

intmain()

{

inta[Size],i,j;

for(i=0;i<Size;i++)

a[i]=i+2;

for(i=0;i<Size;i++)

{

if(a[i])

{

for(j=i+1;j<Size;j++)

if(a[j]%a[i]==0)

a[j]=0;

}

}

for(i=0;i<Size;i++)

if(a[i]!=0)

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

printf(" ");

return0;

}

結果

8. 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）；

｝

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

｝

9. 用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語言