2017计算机学科夏令营上机考试A：判决素数个数（素数的判断、素数表）

思路分析

本题是一道模板题，求出素数表，计数在X、Y之间的素数个数即可。注：此处X、Y的大小关系并没有给出！
方法一： 对每个数进行素数判断；
方法二： 素数筛选法——从2开始遍历，素数的倍数一定是非素数。

代码——方法一

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

bool isPrime(int n) // 判断素数
{
    if(n <= 1)
    {
        return false;
    }
    int sqr = (int)sqrt(n*1.0);
    for(int i=2; i<=sqr; i++)
    {
        if(n%i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
    if(y < x) // 题中没说x、y的大小关系
    {
        swap(x, y);
    }
    int ans = 0;
    for(int i=x; i<=y; i++)
    {
        if(isPrime(i))
        {
            ans++;
        }
    }
    printf("%d", ans);

    return 0;
}

代码——方法二

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 100010;
int flag[maxn]; 

void findPrime() // 得到素数表
{
    for(int i=2; i<maxn; i++)
    {
        if(flag[i] == 1) // 找到第一个素数，其倍数都为非素数
        {
            for(int j=i+i; j<maxn; j+=i)
            {
                flag[j] = 0; // 置为非素数
            }
        }
    }
}

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
    if(y < x)
    {
        swap(x, y);
    }
    fill(flag, flag+maxn, 1);  // 先假设所有数都为素数
    flag[1] = 0; // 1不是素数
    int ans = 0;
    findPrime();
    for(int i=x; i<=y; i++)
    {
        ans += flag[i];
    }
    printf("%d", ans);

    return 0;
}