本题代码可以参考这里。


原题： 1013. 数素数 (20)

令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

注意

时间限制： 100 ms
内存限制： 65536 kB
代码长度限制： 8000 B
判题程序： Standard
作者： CHEN, Yue



题目分析

判断某个数是否为素数是一类很重要的题目。可以仅根据素数定义遍历判断，但容易超时。需要对算法进行优化，但又不能太复杂，否则临场容易出错。

PS：超时的原因 a).取余运算耗时；b).进行了大量取余运算。

  1. 基本优化

    • 大于2的素数都是奇数
    • 如果N没有[2, sqrt(N)]之间的素因子，那么N是素数

    基于以上两点，可以节省很多不必要的判断时间。（偶数，(sqrt(N), N) 全部跳过）

    int is_prime(int num){
    int up_bound=0, divisor=1;
    if( 2<num && num%2){
        up_bound = (int)sqrt(num);
        for(divisor=3; divisor<=up_bound; divisor+=2){
            if( 0 == num % divisor )
                return 0;
        }
        return 1;
    }else if(2 == num)
        return 1;
    else
        return 0;
}

    这个算法，C可以轻松通过时间限制。python就吃力了，PN较大的时候会超时。

  2. 筛表法

    筛表法是一种用空间换时间的方法。这个方法不是说给定一个数，然后去取余啥的判断是否为素数，而是首先整理出一定范围内(比如1到1000之间)所有的素数，称为素数表，然后判断给定的数是否在素数表里面。

    参考这篇博客

    素数筛法是这样的：
1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.
2.然后：
for( i=3; i<=sqrt(n); i+=2 ){
    if(prime[i])
    for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。

原理很简单：
当i是质(素)数的时候，i的所有的倍数必然是合数。
如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质数的倍数筛掉。

    这个算法有一点需要注意，那就是素数表大小的选择。用1的方法跑一下程序，可以发现题目要求的第10000个素数是104729，比例大概是1/11。所以需要大致了解一下一定范围内，素数占自然数的比例。先看代码

    #define MAX 300001
/*
...	
*/

bool prime_list[MAX] = {false, false, true};
for(i=3; i<MAX; i+=2){
    prime_list[i] = true;
    prime_list[i+1] = false;
}

up_bound = (int)sqrt(MAX);
for(i=3; i<=up_bound; i+=2){
    if(prime_list[i]){
        for( j=i+i; j<MAX; j+=i){
            prime_list[j] = false;
        }
    }
}

    MAX不能太小，比如MAX=100001，那么就选不到第10000个素数了。对于C，MAX可以设为很大，比如MAX=300001，程序跑下来时间只有几个ms。

    但是在用python实现这个算法时，如果选MAX=300001，那么每个测试样例都会超时。我的做法是MAX随输入变化，MAX=PN*10+5001，最大耗时76ms<100ms，按照10000/100000，再加10001大概多10%的时间，比例系数和常数项可以通过本地测试的结果确定，耗时达标即可。

    对比下可以发现，C的时间效率大概是python的10~20倍，内存效率10倍。

  3. 其他方法

    2和3非常容易理解与记忆，对于普通OJ已经够用。当然还有更高效但更复杂的方法，但是临场不一定会用，这里就不再班门弄斧了。

    //另外有一个trick，先本地把一定范围内的素数全部打出来，也就是本地直接生成素数表，然后…

    //不知道算不算作弊，紧急情况用。

部分测试用例

  • test1

    输入
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

  • test2

    输入
10000 10000

输出
104729

其他参考

  • 素数判断算法(高效率）

  • 算法总结：判断一个数是否为素数

  • 数论部分第一节：素数与素性测试

  • 在线判断质数（素数）

  • WolframAlpha: prime 10000

  • 算术基本定理

  • 分解质因数

  • PAT_B_1007: 素数对猜想

  • [题目分析]—[第1节]—[基本优化]中两个前提条件的证明。

    第一点很好证明。主要证第二点：【如果N没有[2, sqrt(N)]之间的素因子，那么N是素数】

    首先根据定义，1不是素数。
其次，我们用反证法证明其逆否命题： 【若N是合数，那么N存在[2, sqrt(N)]之间的素因子】

证明：
设N=a×b, sq=sqrt(N)
根据算术基本定理，设a为素数，b是a以外，N的所有素因子之积

由反证法
i). N的每个素因子都大于sq. ii). a>sq
==> b>sq，a>sq
==> N = a×b > sq×sq > N
等式不成立，原题得证。故其逆否命题也是成立的，即

【如果N没有[2, sqrt(N)]之间的素因子，那么N是素数】

  • [题目分析]—[第2节]—[筛表法]原理的补充证明。

    for( i=3; i<=sqrt(n); i+=2 ){
    if(prime[i])
    for( j=i+i; j<=n; j+=i )
        prime[j]=false;
}

    • 为什么 i<=sqrt(N) 作为循环结束？（参考上面的证明）

    • 为什么 i>sqrt(N) 后面没筛过的奇数都是素数？

      证明：
若sqrt(N)后面的奇数为合数，则其存在 <=sqrt(N)的素因子p。
但内嵌的for循环
	
    for( j=i+i; j<=n; j+=i )
        prime[j]=false;
	
已经确保了含有p这个因子的合数都被标为false，
也就是 >sqrt(N)的数中合数(奇数+偶数)已经被筛掉了，
因此循环结束后， >sqrt(N)的奇数都是素数。


(END)