怎么判斷一個數是素數？

常規的方法是枚舉從2開始的數，看看是否能被整除。

但是，如果要判斷的數很多的時候，那么效率會十分低下.。。。

一個優化的方法是不用判斷比這個數小的所有數（到平方根位置），而是判斷比他小的所有素數。

如果所有小于他的素數都不能將其整除，那么他就是素數。

那么如何快速得到小于他的素數?

有個Eratosthenes

把最后決定采用的寫法放開頭。。不是素數的標記為1

for(int i=2;i*i<=1000000;i++) { if(!isprime[i])for(int j=i;j*i<=1000000;j++) isprime[i*j]=1; }

根據劉汝佳的書的代碼如下：

可是當n為100萬時候竟然直接停止工作！

#include<iostream> using namespace std; const int MAXN=1000+10; int main() {int n;cin>>n;int vis[MAXN],primer[MAXN],count=0;memset(vis,0,sizeof(vis));for(int i=2;i<=n;i++){if(!vis[i]) primer[count++]=i; //將素數存入for(int j=i*i;j<=n;j+=i) //標記是否是素數，如果不存入的話,直接判斷vis[target]是否為0也可以。 vis[j]=1; }for(int i=0;i<count;i++)cout<<primer[i]<<" ";cout<<count<<endl; }

判斷一個數是否是兩個素數的乘積。

多組數據不超過1000組，每組數據一行一個整數n(2 =< n <=1000000)。

n是否是兩個素數的乘積，是輸出Yes，不是輸出No。

下面的寫法是非素數標記為1

聽隊友的改進如下：

#include<cstdio> const int MAXN=1000000+10; bool vis[MAXN]={0};int main() {int count=0;for(int i=2;i*i<=1000000;i++) { for(int j=i;j*i<=1000000;j++) vis[i*j]=1; } int n;while(~scanf("%d",&n)){bool ok=false;for(int i=2;i * i <=n;i+=1){if(vis[i]) continue;int t=n / i;if(t*i==n && !vis[t] ){ok=true;break;}}if(ok)printf("Yes\n");elseprintf("No\n");} }

FZU1563

http://acm.fzu.edu.cn/problem.php?pid=1563

可是在FZU這題直接TLE!搜題解得到如下寫法

#include<cstdio> const int MAXN=1000000+10; const int INF=1000000; bool isprime[MAXN]={0}; int prime[MAXN]; int main() {int pnum=0;for(int i=2;i<=INF;i++) { if(!isprime[i]) prime[pnum++]=i; for(int j=0;j<pnum&&prime[j]*i<=INF;j++) { isprime[prime[j]*i]=1; if(i%prime[j]==0) break; } } int n;scanf("%d",&n);while(n--){int a,b;int cnt=0;scanf("%d%d",&a,&b);for(int i=a;i<=b;i++)if(isprime[i]==0)cnt++;printf("%d\n",cnt);} }

最后改進如下：

#include<cstdio> const int MAXN=1000000+10; const int INF=1000000; bool isprime[MAXN]={0}; int prime[MAXN]; int main() {for(int i=2;i*i<=1000000;i++) { if(!isprime[i])for(int j=i;j*i<=1000000;j++) isprime[i*j]=1; } int n;scanf("%d",&n);while(n--){int a,b;int cnt=0;scanf("%d%d",&a,&b);for(int i=a;i<=b;i++)if(isprime[i]==0)cnt++;printf("%d\n",cnt);} }

轉載于:https://www.cnblogs.com/murmured/p/5004343.html

總結

以上是生活随笔為你收集整理的素数表（Eratosthenes）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。