例54 素数表
问题描述
令 Pi表示第 i 个素数。现任给两个正整数 M≤N≤104 ，请输出 PM到PN的所有素数。
输入格式
输入在一行中给出 M 和 N，其间以空格分隔。
输出格式
输出从 PM到 PN的所有素数，每 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。