PAT-B 1013. 数素数 (20)

传送门

https://www.patest.cn/contests/pat-b-practise/1013

题目

令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

分析

此题困扰了时间还蛮长的,主要就是效率问题,要在100ms内求出第10000个以内的素数,这与求10000以内的素数的计算次数完全不同。我是在参考了别人的代码后才写出来的,还考虑了好久算法的问题,发现了一个规律:一个数,只要它不是素数(质数),那么它肯定至少有一个因子是素数。这个规律我没法去证明,但是还没有发现反例,我就默认这个规律是成立的,然后就有了判断素数的方法isPrimeNumber。
另外值得注意的是,如果你判断n是不是素数,只要判断到√n即可,因为再让其中的一个因子递增,那么另一个因子一定会递减,又与之前的数值重复了,故无需再次判断。
具体算法见函数即可。

源代码

//C/C++实现
#include <stdio.h>
#include <iostream>

using namespace std;

int PNarray[10000] = {2}; //PNarray[0] = 2;

bool isPrimeNumber(int n, int PNarray[]){
    for(int i = 0; PNarray[i] * PNarray[i] <= n; i++){
        if(n % PNarray[i] == 0){
            return false;
        }
    }
    return true;
}

int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    int index = 1;
    for(int i = 3; index < b; i += 2){ //建立到第b个数的素数表
        if(isPrimeNumber(i, PNarray)){ //is prime number
            PNarray[index++] = i; //store in prime number table
        }
    }
    int count = 0;
    for(int j = a - 1; j < b; j++){
        if(count % 10 != 0){
            printf("%c", ' ');
        }
        printf("%d", PNarray[j]);
        count++;
        if(count % 10 == 0){
            printf("%c", '\n');
        }
    }
    if(count % 10 != 0){
        printf("%c", '\n');
    }
    return 0;
}

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器