素數篩模板
❶ 篩法求素數，求詳解！謝謝。用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 環境下測試通過。
以上兩種演算法在小數據下速度幾乎相同。
❷ 用篩法找1-100之間的全部素數。應用程序界面如圖所示，寫出相關的事件代碼。
#include <stdio.h>
#include <math.h>
int main()
{
int i=0; int j=0; int k=0;
char prime[101];//101個數，建立對應的標志數組，為char型，prime[0]沒有用到
prime[0] = 0; prime[1] = 0;
for(i=2; i<=100 ;i++) {
prime[i]=1;
} // 先假設都是素數
for(i=2; i<=100; i++) {
if(prime[i] == 1) {
for(j=i+i; j<=100; j=j+i) { prime[j] = 0; }
}
}
for(i=2; i<=100; i++) //把篩選出的素數列印出來
{
if (prime[i] == 1) { printf("%d is prime number\n",i);
}
return 0;
}
❸ c語言素數篩法
Console.WriteLine("請輸入一個數：");
int i=int.Parse(Console.ReadLine());
int j;
for (j = 2; j < i; j++)
{
if (i % j == 0)
{
Console.WriteLine("否"); break;
}
else if (j == i - 1)
{
Console.WriteLine("是"); break;
}
}
Console.ReadKey();
這段代碼的意思是輸入一個數，先判斷i對j求余是否為0，不為0在篩選出素數
❹ 篩法求素數
void make_prime() {
memset(prime, 1, sizeof(prime));
prime[0]=false;
prime[1]=false;
int N=31700;
for (int i=2; i<N; i++)
if (prime[i]) {
primes[++cnt ]=i;
for (int k=i*i; k<N; k+=i)
prime[k]=false;
}
return;
素數*另一個數都是合數，排掉這個合數，剩下的都是素數
❺ 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;
}
❻ 1000的素數 篩法
#include <stdio.h>
#include <math.h>
main()
{
#define N 100
int i,j,a[N];
for(i=0;i<=N;i++)
a[i]=i+1;
for(i=1;i<sqrt(N);i++)
{
if(a[i])
{
for(j=i+1;j<=N;j++) //應該為 for(j=i+1;j<N;j++)
{
if(a[j])
if(a[j]%a[i]==0)
a[j]=0;
}
}
}
for(i=1;i<N;i++)
if(a[i])
printf("%d\t",a[i]);
}
❼ 計蒜客練習：簡單素數篩法
說實話我這道題也弄了半天 實在不理解它說的（讓數組元素的值作為篩去與否的標志，比如篩去以後讓元素值為1，然後依次輸出就可以了）這段話是什麼意思
我是這么做的
#include <stdio.h>
int N,A,B,C=1;
int main()
{
scanf("%d",&N);
for(A=1;A<N+1;A++)
{
C=1;
for(B=2;B<A;B++)
{
if(A%B==0)
C=0;
}
if((C==1)&&(A!=1))
printf("%d\n",A);}
return 0;
}
N是輸入的數字，A是從1~N之間每個數字，B是從1~A每個數字
❽ 先來一種比較快速的素數篩選法，這是一種非常高效的篩法 #include<stdio.h> #i
#include<stdio.h>
#include<string.h>
#define MAXN 100 //最大處理范圍
int flag[MAXN+1];//質數標識，0表示質數
int main()
{
int i,j;
memset(flag,0,sizeof(flag));
//初始化質數標識為0
for(i=2;i<=MAXN;i++)
//從2開始到最大范圍，去掉所有數的整倍數
{
if(!flag[i])
//如果i未做標識
for(j=i*i;j<=MAXN;j=j+i)
//對i的整倍數做標識，因為小於i的倍數的數，在小於i的數時處理完畢，所以從i*i開始即可
if(!flag[j])
//將整倍數的數標識為1，不是質數
flag[j]=1;
}
for(i=2;i<=MAXN;i++)
if(!flag[i])
//根據篩選結果輸出質數
printf("%d ",i);
printf("\n");
return 0;
}
❾ 篩法求素數
主要問題出在erat_sieve函數的n=n/2;這個語句上了，本來要計算的是200。結果你在這里把n折半，結果就再後面m=sqrt(n);m的取值就不是根號下200而是100結果10以上的素數就沒有做為因子用上，所以直接導致121和169沒有被清除出來。
你這個方法不是篩法吧，篩法是不用除法了求模運算的。我寫個篩法你看看
#include "stdio.h"
#include "math.h"
int main()
{
char prime[10000]={0};
int i,j,n,m;
for(i=3;i<10000;i+=2) prime[i]=1;
prime[2]=1;
printf("輸入整數n（1~n）：");
scanf("%d",&n);
m=sqrt(n);
for(i=3;i<m;i++)
{
for(j=i*2;j<n;j+=i)
{
if(prime[j]) prime[j]=0;
}
}
j=0;
for(i=0;i<n;i++)
{
if(prime[i])
{
printf("%3d ",i);
j++;
if(j%10==0) printf("\n");
}
}
printf("\n%3d ",j);
}
❿ C++ 素數判斷代碼解析 我是剛接觸的C++ 超級菜鳥級別的 求高手幫幫我！
這是篩法求素數
第三步是聲明vector類的以int類型為模板的對象，可以簡單的認為是一個整型數組，（10000，1）的意思是分配一萬個單位，都賦初值為1
4-7步為求素數的過程：
從2開始循環，找到一個標記為素數的（一開始默認全是素數），就將它的倍數全部標記為不是素數（內層循環就是干這個的）
篩法求素數如果不懂可以上網查
接下來是輸出
第8行打開叫a.txt的文件
第9行從文件中循環讀入數字a，直到到達文件結尾（in>>a)，或者數字不在范圍內（a>1&&a<10000)
第10行輸出數字a是否素數（還記得嗎，我們的prime數組是用來標記一個數是不是素數的，如果a是，prime[a]=1，否則，prime[a]=0）