蓝桥杯算法提高VIP-找素数 （C++代码）

            把int改成long long 就对了，太伤心了。。。

            解题思路：一个合数n他的最小质因子不会超过sqrt(n)，所以我们求区间[a,b]的素数，我们只需要

                                找出[2,sqrt(b)]以内的素数，然后将其倍数从[a,b]里面里面去掉就行，最后剩下的就是

                                    [a,b]内的素数了。

            注意：整形存不下，要用long long,区间不要开太大，也不要开太，还有，需要用到线性筛素数筛

                    选素数，普通方法会超时。

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1000001;
bool vis[maxn];        //标记数组，true是素数，false是合数
int ans[maxn];            //存储得到的素数
int tot;
bool isprime[maxn];
void Getprime(int n)                //线性筛素数
{
    vis[1] = true;               //1不是素数
    for (int i = 2; i <= n; i++)   //进行判断
    {
        if (!vis[i])
            ans[tot++] = i;
        for (int j = 0; j < tot&&(ll)ans[j] * i <= n; j++)
        /*用当前数i与i之前的素数相乘取得一个合数*/
        {
            vis[ans[j] * i] = true;
            if (i%ans[j] == 0)   break;
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    Getprime(sqrt(m));            //得到素数表
    int num = m - n + 1;
    for (int i = 0; i < tot; i++)
    {
        for (ll j = (ans[i] + n - 1) / ans[i];;j++)
        /*(ans[i]+n-1)/ans[i]是求区间内的第一个数至少为i的几倍*/
        {
            if (j == 1)
                continue;
            if (ans[i] * j > m)
                break;
            isprime[ans[i] * j - n] = true;    //true则不是素数
        }
    }
    int cnt = 0;
    for (int i = 0; i < num; i++)
    {
        if (!isprime[i]) cnt++;    //    统计素数个数 
    }
    cout << cnt << endl;        
    return 0;
}