B1013 數(shù)素數(shù)（20分）

令 \(P?_i\)表示第 i 個素數(shù)。現(xiàn)任給兩個正整數(shù) \(M≤N≤10^4\)，請輸出 \(P_M\)到 \(P_N\)的所有素數(shù)。

輸入格式：

輸入在一行中給出 M 和 N，其間以空格分隔。

輸出格式：

輸出從 \(P_?M\)到 \(P_N\)的所有素數(shù)，每 10 個數(shù)字占 1行，其間以空格分隔，但行末不得有多余空格。

輸入樣例：

5 27

輸出樣例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

思考

這個問題是否需要篩法？
我覺得是需要的，因?yàn)?0的4次方已經(jīng)很大了，是素數(shù)的個數(shù)達(dá)到10的4次方。
算法筆記上說，篩法和非篩法都可以解決問題。
那么首先用非篩法試一下。
前100009個數(shù)有9593個素數(shù)。所以這里用不用篩法，都可以解決問題前1000009有78499個素數(shù);
每 10 個數(shù)字占 1 行，其間以空格分隔，但行末不得有多余空格。
怎么辦？這種輸出形式。
給出第4個測試點(diǎn)答案錯誤的代碼

#include<cstdio> #include<cstring> #include<cmath> const int MAXN=100009; int prime[MAXN], pNum = 0; bool p[MAXN] = {0}; bool isPrime(int n){if(n<=1) return false;int sqr=(int)sqrt(1.0*n);for(int i=2;i<=sqr;i++){if(n%i==0) return false;}return true; }void Find_Prime(){for(int i = 1; i<MAXN;i++){if(isPrime(i) == true){prime[pNum++] = i;p[i] = true;}} } int main(){Find_Prime();int M,N;int enter=0; scanf("%d %d", &M, &N);for(int i=M-1;i<N-1;i++){printf("%d",prime[i]);enter++;if(enter!=10){printf(" ");}else {printf("\n");enter = 0;}}printf("%d",prime[N-1]); }

不斷擴(kuò)大打表范圍
終于在擴(kuò)大到
const int MAXN=110050;時候AC掉了，估計(jì)是最大的極限的素數(shù)10的4次方的。

轉(zhuǎn)載于:https://www.cnblogs.com/lingr7/p/10292015.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的B1013 数素数（20分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。