质数，埃氏筛

质数：又称素数；除1和他本身外，不被其他自然数整除，否则为合数。

第一种：暴力筛选法

找质数最基础的方法：

bool isprime(int n)
{
    if(n<2)return false;
    for(int i=2;i<n;i++)
    {
        if(n%i==0)return false;
    }
    return true;
}

根据上面方法时间复杂度为O(n)

可以稍微优化

bool isprime(int n)
{
    if(n<2)return false;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)return false;
    }
    return true;
}

第二种：埃氏筛（最常用）

在求指定范围内的质数个数问题上，埃氏筛的方法比较优

一般都是用一个数组存是否为质数

const int MAXN=1e5;
bool num[MAXN+5];
void isprime()
{
    //memset(num,true,sizeof(num));
    for(int i=2;i<=MAXN;i++)
    {
        if(!num[i])//num[i]
        {
            for(int j=i;j<=MAXN;j++)
            {
                num[i*j]=true;
                //num[i*j]=false;
			}
        }
    }
}

优化一：第二个循环优化

for(int i=2;i<=MAXN;i++)
{
	if(!num[i])
    {
        for(int j=i*i;j<=MAXN;j+=i)
        {
            num[j]=true;
        }
    }
}

例1：素数的和

描述
Alice想把一个不大于100000的数分解成多个（至少2个）不同的素数的和，请帮她看看有多少种不同的分解方法。因为方法数量可能非常多，因此要求输出该值除以100000007的余数。素数是大于等于2，且只有1和自身两个因数的整数。
输入
一个正整数T，表示案例的数量。（T<=1000）每组案例中，有一个正整数n，表示待分解的数。（1<=n<=100000）
输出
针对每组案例，输出一个整数，表示n能分解成至少两个不同素数之和的方案数量除以100000007的余数。注意5=2+3和5=3+2是同一种方案。每组案例输出完都要换行。
样例输入
2514
样例输出
12
提示说明
5=2+3，但不能5=5，因为要求至少2个不同素数之和。14=3+11，14=2+5+7，但不能14=7+7，因为素数必须不同。

解题方法：

首先使用埃氏筛，将质数储存在prime数组中

#include "bits/stdc++.h"
using namespace std;
const int M = 1e5 + 5;
const int mod = 100000007;
int prime[M]; //储存质数
bool vis[M]; //判断质数
int num[M]; //
int main() {
    int cnt = 0;
    for (int i = 2; i <= M; ++i)
    {
        if (!vis[i])
        {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j)
        {
            if (i * prime[j] > M)//判断是否越界
                break;
            vis[i * prime[j]] = true;//筛数
            if (i % prime[j] == 0)
                break;
        }
    }
    num[0] = 1;
    vis[1] = true;
    //
    for (int i = 2; i < M; ++i) 
    {
        if (!vis[i]) //是质数
        {
            for (int j = M - 1; j >= i; j--) //从后到该质数
            {
                //从小到大记录质数和的数量，即质数本身组合质数数量加上另一数的组合质数数量
                num[j] = (num[j] + num[j - i]) % mod;
            }
        }
    }
    int T;
    scanf("%d", &T);
    while (T--) 
    {
        int n;
        scanf("%d", &n);
        printf("%d\n", num[n] - !vis[n]);//（-!vis[n]）为了1和0与
        //至少两个的限制：只有本身，且为质数
    }
    return 0;
}

例2：源数（埃氏筛应用）

描述
如果x的所有因数的和等于y，则称x是y的源数。给定一个正整数a，求a的源数。
输入
多组案例。一个正整数n，表示案例的数量。（n<=50）每组案例由一个正整数a构成。（a<=1000000）
输出
针对每组案例，输出一个整数，表示a的源数。如果有多个满足条件的源数，从小到大输出所有满足条件的源数，两两之间用一个空格字符隔开。如果没有满足条件的源数，则输出0。每组案例输出完都要换行。

主要代码：

for (int i = 1; i < 1000005; i++)
    {
        for (int j = i; j < 1000005; j += i)
        {
            a[j] += i;//数组记录和
        }
    }

例三：质数乘积（埃氏筛应用）

确定一个正整数是否恰好能分解成两个不同的质数相乘的结果。

解题方法：

利用埃氏筛将质数筛选出来，通过输入的正整数开循环找能被整除的质数且判断另一除数是否为质数

for (int i = 2; i * i < a; i++)
{
    if (!num[i] && a % i == 0 && !num[a / i])
    {
        cout << "Yes" << endl;
        f = 0;
        break;
    }
}

例四：寻找数字和

涂涂又在给越越出难题了（实际并不难），涂涂对越越说，我有一个数字 n 和一个数字 k，你需要找到 n 个互不相同的正整数，保证它们两两之间的最大公因数为 k，越越日常卑微，你能帮帮他吗？

针对每组案例，由于符合要求的数字组合不止一种，所以你只需要输出这 n 个数字和最小的那个答案对1000000007取模以后的结果，然后换行。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod = 1000000007;
const ll MAXN = 2e6 + 5;
bool a[MAXN];//筛选
int p[MAXN];//记录公因数
int main()
{
	ll x = 1;
	p[x++] = 1;
	for (ll i = 2; i < MAXN; i++)
	{
		if (!a[i])
		{
			p[x++] = i;
			for (ll j = i; j < MAXN; j += i)
			{
				a[j] = true;
			}
		}
	}
	for (int i = 1; i < x; i++)
	{
		p[i] += p[i - 1];
		p[i] %= mod;
	}
	int T;
	cin >> T;
	while (T--)
	{
		ll n, k;
		cin >> n >> k;
		cout << p[n] * k % mod << endl;
	}
	
	return 0;
}

例五：tql和她的数学题(埃氏筛与前缀和)

众所周知 tql 很喜欢研究数学题，最近她又遇到了这样一个数学题，令 f(x) = (x 的因子个数)，求对于所有 L <= i <= R，f(i) 之和（即 ∑f(i)，L <= i <= R），当 tql 看到题目的那一刻她就已经完全懂了, 但她想要考考你能不能做出来。

例：f(12) = 6，因为 1、2、3、4、6、12 都是 12 的因子，共 6 个。

针对每组案例，输出 ∑f(i)，其中 L <= i <= R，然后换行。

//埃氏筛
for (ll i = 1; i <= 200005; i++)
{
    for (ll j = i; j <= 200005; j+=i)
    {
        num[j]++;
    }
}

//前缀和
for (ll i = 1; i < 200005; i++)
{
    num[i] = num[i - 1] + num[i];
}

//[L,R]范围内的个数
num[R] - num[L - 1]