例54 素數表
問題描述
令 P?i表示第 i 個素數，現任給兩個正整數 M≤N≤10?4?? ，請輸出 P?M到P?N的所有素數，
輸入格式
輸入在一行中給出 M 和 N，其間以空格分隔，
輸出格式
輸出從 P?M?到 P?N的所有素數，每 10 個數字占 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
（1）編程思路，
定義陣列int primes[10001];，其中元素prime[i]保存第i+1個素數，顯然，prime[0]=2，即2是第一個素數，且記錄當前找到的素數個數pc=1，
之后，對從3開始的每個奇數num進行判斷，若已找到的pc個素數（primes[0]~ primes[pc-1]）均不是num的約數，則num就是一個素數，保存起來primes[pc++]=num，
通過預處理求出了前10000個素數后，對于輸入的M 和 N，按要求輸出第M 到第N個之間的素數即可，
（2）源程式，
#include <stdio.h>
int main()
{
int primes[10001];
int pc,num,k;
primes[0]=2; // 2是第一個素數
pc=1; // 已有第一個素數
num=3; // 被測驗的數從3開始
while (pc<10000)
{
k=0;
while(primes[k]*primes[k]<=num)
if (num%primes[k]==0)
{
num+=2;
k=1;
}
else
k++;
primes[pc++]=num;
num+=2; // 除2外，其余素數均是奇數
}
int m,n,cnt=0;
scanf("%d%d",&m,&n);
for (k=m;k<=n;k++)
{
printf("%d ",primes[k-1]);
cnt++;
if (cnt%10==0) printf("\n");
}
printf("\n");
return 0;
}
習題54
54-1 線性篩素數
問題描述
給定一個范圍n，有q 個詢問，每次輸出第k小的素數，
輸入格式
第一行包含兩個正整數 n，q，分別表示查詢的范圍和查詢的個數，（1≤n≤108，1≤q≤106），保證查詢的素數不大于 n，
接下來q行每行一個正整數 k，表示查詢第k小的素數，
輸出格式
輸出 q 行，每行一個正整數表示答案，
輸入樣例
100 5
1
2
3
4
5
輸出樣例
2
3
5
7
11
（1）編程思路1，
1~108之間的素數超過5百萬個，像例54那樣預處理出這5百萬個素數并保存起來，復雜度較高，會超時的，下面采用篩法求第k個素數，
埃氏篩的思想是：要得到n以內的所有素數，就要把不大于sqrt(n)的素數的倍數全部篩除，剩下的就是素數，具體做法是：
定義一個陣列char isPrime[100000010]，初始值全為1，isPrime[i]=1表示整數i在篩子中，是一個素數；isPrime[i]=0表示整數i是一個合數，從篩子中篩除了，定義陣列int Prime[6000001];保存依次求得的素數，變數len記錄求得的素數表中素數的個數，初始值為0，
從2開始，2是一個素數，保存到素數表中Prime[++len]=2，然后把2的倍數j（不包括2本身）標記為合數（isPrime[j]=0）；然后向后列舉查詢，每查到一個未標記為合數的整數i（即isPrime[i]==1），就把它保存到素數表中Prime[++len]=i，再把它的倍數（不包括i本身）標記為合數，以此類推，直到查到n 為止，
（2）源程式1，
#include <stdio.h>
#include <string.h>
char isPrime[100000010];
int Prime[6000001];
int main ()
{
int n,q;
scanf("%d%d",&n,&q);
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
int len=1;
int i,j;
for (i=2;i<=n;i++)
{
if (isPrime[i]) //如果是素數
{
Prime[len++]=i;
for (j=2*i;j<=n;j+=i) // 將它的倍數記為合數
{
isPrime[j]=0;
}
}
}
while (q--)
{
int k;
scanf("%d",&k);
printf("%d\n",Prime[k]);
}
return 0;
}
將上面的源程式1提交給洛谷P3383（https://www.luogu.com.cn/problem/P3383）不能Accepted，測驗點#3、#4和#5均顯示TLE，超時了，
這主要是由于埃氏篩的效率還是低了些，例如，源程式1中一個整數30，它會被2,3,5三個數標記為合數，這就重復了兩次，更大的數同理，如何快速地篩出一定上限內的素數呢？
（3）編程思路2，
為了提高篩法的效率，可以采用歐拉篩，歐拉篩法的基本原理是每個合數通過其最小素因子來篩除，這樣可以保證每個和數只被篩除一次，從而提高篩法的效率，
篩除程序同樣從2開始，用變數i回圈遍歷2~n之間的每個整數，初始時，isPrime[i]均為1，表示i在篩子中，是一個素數，
i=2時，isPrime[2]=1，2是一個素數，保存到素數表中Prime[++len]=2，素數表中有一個素數（2），然后素數表中每個素數的2倍數i*Prime[j]（1≤j≤len-1）標記為合數，即isPrime[4]=0，篩掉了整數4；
i=3時，isPrime[3]=1，3是一個素數，保存到素數表中Prime[++len]=3，素數表中有2個素數（2和3），然后將素數表中每個素數的3倍數i*Prime[j]（1≤j≤len-1）標記為合數，即isPrime[6]=0，isPrime[9]=0，篩掉了整數6和9；
i=4時，isPrime[4]=0，4不是一個素數，不保存，素數表中還是2個素數（2和3），然后將素數表中每個素數的4倍數i*Prime[j]（1≤j≤len-1）標記為合數，即isPrime[8]=0；但這時要注意，由于4%2==0，即4是2的倍數，不能再繼續篩；因為若繼續篩，會篩除12（3*4），這樣12就不是用最小素因子2來篩除了，因此，i=4時只能篩掉整數8；
由此，在篩除回圈中，用陳述句if (i % Prime[j] == 0) break;來保證這點，
i=5時，isPrime[5]=1，5是一個素數，保存到素數表中Prime[++len]=5，素數表中有3個素數（2、3、5），然后將素數表中每個素數的5倍數i*Prime[j]（1≤j≤len-1）標記為合數，即isPrime[10]=0，isPrime[15]=0，isPrime[25]=0，篩掉了整數10、15和25；
i=6時，isPrime[6]=0，6不是一個素數，不保存，素數表中還是3個素數（2、3和5），然后將素數表中每個素數的6倍數i*Prime[j]（1≤j≤len-1）標記為合數，即isPrime[12]=0；同樣，由于6%2==0，即6是2的倍數，不能再繼續篩；因為若繼續篩，會篩除18和30，因此，i=6時只能篩掉整數12；18和30到后面用2*9和2*15來篩除，
i=7時，會篩除14（2*7）、21（3*7）、35（5*7）和49（7*7）四個數；
i=8時，只會篩除16（2*8）這1個數；
i=9時，只會篩除18（2*9）、27（3*9）這2個數；
……
顯然，由于歐拉篩法每個合數只用其最小素因子篩除1次，由此可提高效率，
（4）源程式2，
#include <stdio.h>
#include <string.h>
char isPrime[100000010];
int Prime[6000001], cnt = 0;
int main()
{
int n, q;
scanf("%d %d", &n, &q);
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = 0;
int i,j;
for (i=2; i<=n; i++)
{
if(isPrime[i])
Prime[++cnt] = i;
for (j=1; j<=cnt && i*Prime[j]<= n; j++)
{
isPrime[i*Prime[j]] = 0;
if (i % Prime[j] == 0)
break;
}
}
while (q--)
{
int k;
scanf("%d", &k);
printf("%d\n", Prime[k]);
}
return 0;
}
將上面的源程式2提交給洛谷P3383（https://www.luogu.com.cn/problem/P3383）可以Accepted，
54-2 素數個數
問題描述
求1,2,?,N 中素數的個數，
輸入格式
一行一個整數 N（1≤N≤108），
輸出格式
一行一個整數，表示素數的個數，
輸入樣例
10
輸出樣例
4
（1）編程思路，
定義陣列char a[100000005]={0};表示篩子，初始時各元素值全為0，a[i]=0表示整數i在篩子中，是一個素數；a[i]=1表示整數i是一個合數，從篩子中篩除了，
為求1~n中素數的個數，可以定義變數ans=n-1，表示初始時有n-1個素數（因為1不是素數），
之后按埃氏篩的思想進行操作，每次篩除一個還在篩子中的合數，ans減1，篩到sqrt(n)的倍數后結束篩除程序，此時ans的值就是1~n之間素數的個數，
（2）源程式，
#include <stdio.h>
char a[100000005]={0};
int main ()
{
int n;
scanf("%d",&n);
int ans=n-1;
int i,j;
for (i=2;i*i<=n;i++)
{
if (a[i]==0) //如果是素數
{
for (j=i*i;j<=n;j+=i) // 將它的倍數記為合數
{
if (a[j]==0)
{ a[j]=1; ans--; }
}
}
}
printf("%d\n",ans);
return 0;
}
54-3 自我數
問題描述
對于每一個正整數n，我們定義d(n)為n加上它每一位數字的和，例如，d(75)=75+7+5=87，給定任意正整數n作為一個起點，都能構造出一個無限遞增的序列：n，d(n)，d(d(n))，d(d(d(n)))，…例如，如果從33開始，下一個數是33+3+3=39，再下一個為39+3+9=51，再再下一個為51+5+1=57，因此所產生的序列就像這樣：33，39，51，57，69，84，96，111，114，120，123，129，141，…數字n被稱作d(n)的發生器，在上面的這個序列中，33是39的發生器，39是51的發生器，51是57的發生器等等，有一些數有超過一個發生器，如101的發生器可以是91或100，一個沒有發生器的數被稱作Self-Number，如前13個Self-Number為1，3，5，7，9，20，31，42，53，64，75，86，97，我們將第i個Self-Number表示為a[i]，所以a[1]=1，a[2]=3，a[3]=5，…，
輸入格式
輸入包含整數N、K、s1. . . sk，其中1<=N<=10^7，1<=K<=5000，以空格和換行分割，
輸出格式
在第一行你需要輸出一個數，這個數表示在閉區間[1, N]中Self-Number的數量，第二行必須包含以空格劃分的K個數，表示a[s1]. . a[sk]，這里保證所有的a[s1]. . a[sk]都小于N，（例如，如果N=100，sk可以為1-13，但不能為14，因為a[14]=108>100）
輸入樣例
100 10
1 2 3 4 5 6 7 11 12 13
輸出樣例
13
1 3 5 7 9 20 31 75 86 97
（1）編程思路1，
定義陣列char vis[10000001]={0};表示一個篩子，初始時各元素值全為0，vis[i]=0表示整數i在篩子中，是一個自我數；vis[i]=1表示整數i有發生器，不是一個自我數，從篩子中篩除了，在定義陣列int ans[1000001]保存找到的自我數，ans[i]的值是第i個自我數，
從1開始，vis[1]=0，1是一個自我數，保存到ans陣列中ans[++len]=1，然后把以1作為發生器可產生的一連串不超過n的整數標記為非自我數，從篩子中篩除，篩除序列為2，4，8，16，23，28，38，…；然后向后列舉查詢，每查到一個未標記為非自我數的整數i（即vis[i]==0），就把它保存到ans陣列中ans[++len]=i，再把以i作為發生器可產生的一連串不超過n的整數標記為非自我數，從篩子中篩除，例如，vis[3]=0，3是一個自我數，ans[++len]=3，然后篩除序列3，6，12，15，21，24，30，33，39，51，57，69，84，96，111，114，120，123，129，141，…中的各數；以此類推，直到查到n 為止，
（2）源程式1，
#include <stdio.h>
int ans[1000001];
char vis[10000001]={0};
int next(int num)
{
int res=num;
while(num!=0)
{
res+=num%10;
num/=10;
}
return res;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int i,cnt=0;
for (i=1;i<=n;i++)
{
if (vis[i]==0)
{
ans[++cnt]=i;
int now=next(i);
while (now<=n && vis[now]==0)
{
vis[now]=1;
now=next(now);
}
}
}
printf("%d\n",cnt);
int t;
for (i=1;i<=k;i++)
{
scanf("%d",&t);
printf("%d ",ans[t]);
}
return 0;
}
將源程式1提交給洛谷題庫P1900（https://www.luogu.com.cn/problem/P1900）只能獲得80分，測驗點#6和#7顯示MLE，陣列vis占用空間超過了題目的約定，
（3）編程思路2，
如何減少記憶體空間的使用，以避免MLE呢？
實際上表示篩子的陣列vis無需定義太大，若采用回圈陣列的思想，定義 char vis[100];即可，
之所以可以這樣做，是基于兩點：1）任意正整數p作為一個起點，都能構造出一個無限遞增的序列，而我們在查找自我數的程序也是遞增的從1到n，所以一個數無需擴展一連串序列，只需擴展一個數為非自我數即可；2）一個數x與其擴展的下一個數差值最多不超過63，因為最大的7位整數9999999作為發生器生成的下一個整數為9999999+7*9=9999999+63，
由于序列擴展時，后擴展的一個大的數產生的下一個數不一定比先擴展的小的數產生的下一個數大，例如，9作為發生器生成18，而11作為發生器生成13，13<18，而要利用回圈陣列，擴展出的新數最好也是遞增地，因此，擴展時就不是對每個數都直接求其序列發生器中的下一個數，
我們知道，若n是1位數，則n的2倍數2*n=n+n肯定不是自我數，因此對回圈列舉到的1~9，均可篩除其2倍數，在篩除時采用j值進行標記，初始值j=0，每列舉一個數，j=j+2，且置vis[j]=1，
當i=1時，vis[1]=0，1是自我數，保存，且篩除2，j=j+2，vis[j]=vis[2]=1；
當i=2時，vis[2]=1，2不是自我數，也不保存，且篩除4，j=j+2，vis[j]=vis[4]=1；
當i=3時，vis[3]=0，3是自我數，保存，且篩除6，j=j+2，vis[j]=vis[6]=1；
當i=4時，vis[4]=1，4不是自我數，也不保存，且篩除8，j=j+2，vis[j]=vis[8]=1；
當i=5時，vis[5]=0，5是自我數，保存，且篩除10，j=j+2，vis[j]=vis[10]=1；
……
當i=9時，vis[9]=1，9是自我數，保存，且篩除18，j=j+2，vis[j]=vis[18]=1；
當i=10時，vis[10]=1，10不是自我數，也不保存，但從9到10產生了進位，可以將10看成在9的基礎上多了1，以10作為發生器產生下一個數j=10+1=11，置vis[j]=1，即篩除11，
之后11~19均可按成在10的基礎上加1~9，每次不產生進位，處理類同上面，
當i=11時，vis[11]=1，11不是自我數，不保存，j=j+2，vis[j]=vis[13]=1，篩除13；
……
當i=19時，vis[19]=1，19不是自我數，不保存，j=j+2，vis[j]=vis[29]=1，篩除29；
當i=20時，vis[20]=0，20是自我數，保存，但從19到20又產生了進位，以20作為發生器產生下一個數j=20+2=22，置vis[j]=1，即篩除22，
之后21~29均可按成在20的基礎上加1~9，每次不產生進位，處理類同上面，
……
由于每次往前擴展一個數，因此，將上面的下標i和j均修改為i%100和j%100，以此使陣列空間滾動利用起來，另外，每次判斷vis[i%100]后，置vis[i%100]=0，表示新滾動出的下一個陣列位置對應的整數初始時在篩子中，
（4）源程式2，
#include <stdio.h>
int ans[1000001];
char vis[100]={0};
int next(int num)
{
int res=num;
while(num!=0)
{
res+=num%10;
num/=10;
}
return res;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int i,j=0,cnt=0;
for (i=1;i<=n;i++)
{
if (vis[i%100]==0)
ans[++cnt]=i;
else
vis[i%100]=0;
if (i%10==0) j=next(i);
else j+=2;
vis[j%100]=1;
}
printf("%d\n",cnt);
int t;
for (i=1;i<=k;i++)
{
scanf("%d",&t);
printf("%d ",ans[t]);
}
return 0;
}
將源程式2提交給洛谷題庫P1900（https://www.luogu.com.cn/problem/P1900），可以Accepted，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/418042.html
標籤：C
上一篇：從tweepyAPI請求資料時無法呼叫錯誤“dict”物件
下一篇：Go之Logrus用法入門