两个数，求两个数之间素数的个数，数据非常大。

题目描述
给你两个数，求两个数之间素数的个数。

输入：

输入有两个数，一个a，一个b，求a到b之间素数的个数
其中1<=a<=b<=1e12
其中b-a<=1e7

输出：

一个数，表示a-b之间素数的个数。

样例输入：

1 10

样例输出：

4

#include <stdio.h>
#include<math.h>


bool isPrime(int num)
{
    int i = 2;
    if(num <= 1)
    {
        return false;
    }

    int sqrNum = sqrt(num);

    for(i = 2; i <= sqrNum; i++)
    {
        if(num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int getPrimeCount(int a, int b)
{
    int sum = 0;
    if(a > b)
    {
        return sum;
    }

    for(; a <= b; a++)
    {
        if(isPrime(a))
        {
            sum++;
        }
    }
    return sum;
}

int main()
{
    int a, b;
    printf("input two num:\n");
    scanf("%d %d", &a, &b);
    printf("sum is %d\n", getPrimeCount(a, b));
}

两个函数，分别是判断是否为素数，和获取两个数之间素数的个数。为了快速得出是否为素数，这里只判断小于该数的开方的数能否被除尽。

#include <bits/stdc++.h>
using namespace std;

#define max1 1000007
#define max2 10000007
bool prime[max1], big_prime[max2];//分别是1e6内素数和a-b之间素数

void init()//求出1e6内所以素数
{
    memset(prime, 1, sizeof(prime));
    memset(big_prime, 1, sizeof(big_prime));//1为素数，0为非素数
    prime[0] = prime[1] = 0;//特殊情况，0和1不是素数
    for (int i = 2; i*i<max1; i++)
    {
        if (prime[i])
        {
            for (int j = i*i; j<max1; j += i)
            {
                prime[j] = 0;
            }
        }
    }
}

int main()
{
    init();
    long long head, tail;
    cin >> head >> tail;
    for (int i = 2; i<max1; i++)
    {
        if (prime[i])
        {
            for (long long j = head / i; j*i <= tail; j++)
            {
                if (j*i >= head&&j>1)big_prime[j*i - head] = 0;
            }
        }
    }
    if (head == 1)big_prime[0] = 0;//特殊情况
    int ans = 0;
    for (int i = 0; i <= tail - head; i++)
        if (big_prime[i])
            ans++;

    cout << ans;
    return 0;
}

两次素数筛求解

素数生成的规律至今数学家都还没搞明白吧，估计没啥好的简化方法
遍历筛选吧