15 素数筛法

题目来源和说明

题目来源于2009年哈尔滨工业大学计算机研究生机考真题

题目描述

给定一个数字n,要求判断是否是素数（0,1,负数字都是非素数）

样例

输入

13
1

输出
yes
no

简要分析

素数判断，从2-sqrt(n)找是否能够整除的因子即可。

C++ 代码

#include<iostream>
#include<math.h>
using namespace std;

bool judge(int x) {
    if(x<=1) return false;
    //前计算出来，能够保证sqrt仅算一次
    int bound=(int)sqrt(x)+1; //计算枚举上界，为防止double值带来的精度损失，所以采用取整加一
    for(int i=2;i<bound;i++) {
        if(x%i==0) return false;
    }
    return true;
}

int main() {
    int x;
    while(scanf("%d",&x)!=EOF) {
        if(judge(x)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

简要分析

拿到这个题目，可能会想，我们一次枚举每个数字，然后按照上文中判断某个数字是否为素数的方法确定是否为素数，直到得出该区间中所有的素数。当然这样做是可行的，但是该方法的时间复杂度过高。这里提出了一种更优雅的方法解决该问题。

首先考虑这样一个命题：如果一个数不是素数，则必然存在一个小于它的素数为其的因子。这个命题显然是正确的。那么，假如我们已经获得了小于一个数字的所有素数，那么我们只需确定该数字不能被这些素数整除，这个数即为素数。但是这样的作法似乎仍然需要大量的枚举测试工作，正因为如此，我们可以换另一个角度，再我们获得一个素数时，即将它的所有倍数均标记为非素数，这样当我们遍历到一个数时，它没有被任何小于它的素数标记为非素数，则我们确定其为素数。

我们按照如下步骤完成工作：从2开始遍历2到1000000的所有整数，若当前整数没有因为它是某一个小于其的素数的倍数而被标记成非素数，则判定其为素数，并标记它所有的倍数为非素数，然后继续遍历下一个数，直到遍历完2到1000000区间内所有的整数，此时，所有没被标记成非素数的数字即为我们要求的素数。

C++代码

#include<iostream>

using namespace std;
int prime[10000]; //筛选的素数
int primeSize;
bool mark[10001]; //若mark[i]为true,则说明该数字i已经被标记成非素数

void init() { //素数筛法
    for(int i=1;i<=10000;i++) { //初始化
        mark[i]=false;
    }
    primeSize=0;
    for(int i=2;i<=10000;i++) {
        if(mark[i]==true) continue; //若该数字被标记，则跳过
        prime[primeSize++]=i; //否则，得到一个新的素数
        for(int j=i*i;j<=10000;j+=i) { //该数字倍数标记成非素数
            mark[j]=true;
        }
    }
}

int main() {
    init();
    int n;
    while(scanf("%d",&n)!=EOF) {
        bool first=true;
        for(int i=0;i<primeSize;i++) {
            if(prime[i]<n&&prime[i]%10==1) {
                if(first==true) {
                    printf("%d",prime[i]);
                    first=false;
                }
                else printf(" %d",prime[i]);
            }
        }
        if(first) { //说明不存在
            printf("-1\n");
        }
        else printf("\n");
    }
    return 0;
}

分析代码

上面的代码就是素数赛法，即在处理输入的数字前，先处理出2到10000区间内所有的素数。当输入n时，则依次比较已经得到的素数是否符合条件，若符合条件则输出，否则继续比较下一个素数。你可能已经注意到，筛选的时候我们使用了一个小技巧，当判定i为素数，要标记其所有倍数为非素数时候，我们并没有从2i 开始标记而是直接从 ii 开始标记。其原因是显然的， i * k （k<i）必然已经在求k的某个素因数（必然小于i）时标记过了，即i* k同时也是k的素因数的倍数。所以这里，我们可以直接从i的平方开始标记起。尽可能地避免重复工作进而优化程序。

Prime Number

简要分析

该题还是用上题的数据预处理就行，但是这里有一个问题，一开始我mark[10000]的时候，数据部分不正确。这时不难想到是数据的范围太小了，于是我在第14行代码换成了

printf("%d:%d\n",primeSize++，i），

测试了一下，大概数据范围需要取到120000,可以有10000个素数。于是修改后这个题就AC了。其实细细想来这个120000取得也挺关键得，小了可能不够10000个素数，大了可能会导致prime数组越界。

C++代码

#include<iostream>
using namespace std;


int prime[10000];
int primeSize;
bool mark[120000]; //经过测试1~120000范围内有10000个左右素数

void init() {
    for(int i=1;i<=120000;i++) mark[i]=false;
    primeSize=0;
    for(int i=2;i<=120000;i++) {
        if(mark[i]==true) continue;
        prime[primeSize++]=i;
        for(int j=i*i;j<=120000;j=j+i) mark[j]=true;
    }
}
int main() {
    int k;
    init();
    while(scanf("%d",&k)!=EOF) {
        printf("%d\n",prime[k-1]);
    }
    return 0;
}

GoldBach's Conjecture

解释说明

目前没找到可以测试得平台，先搁置后续在补

简要分析

C++代码

高校夏令营机试训练文章被收录于专栏

Leetcode题目太多，不知道如何准备高校夏令营？欢迎关注本专栏，和本小白一起准备夏令营吧！本专题的规划如下：截止到4月下旬：以王道考研为依托，提供夏令营机考的准备计划，打好基础截止到5月中旬：以剑指offer进一步加强本专题的内容如下： 1. 给出题目的在线测试链接，方面您检查代码的正确性 2. 给出题解