质数与合数

判断质数

显然，每个合数都会有相对较小的质因子。

若 \(a\) 为合数，则 \(a = p\cdot q(p,q>1)\)。易证 \(p、q\) 中一定有一个不超过 \(\sqrt a\)（若两个都超过 \(\sqrt a\)，则 \(p\cdot q > a\)）。

更严格地，若 \(a\) 为合数，则一定存在质数 \(p|a\)，且 \(p \leq \sqrt a\)。

bool is_prime(int x)
{
	for (int i = 2; i * i <= x; i++)
    	if (x % i == 0) return false;
    return true;
}

埃拉托斯特尼筛法

考虑这样一件事情：对于任意一个大于 \(1\) 的正整数 \(n\) ，那么它的 \(x\) 倍就是合数\(x > 1\)。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

vector<int> prime;
bool no_prime[N];

void Eratosthenes(int n)
{
    no_prime[0] = no_prime[1] = true;
    for (int i = 2; i <= n; i++)
    {
		if (!no_prime[i])
        {
			for (int j = i << 1; j <= n; j += i)
            {
                no_prime[i] = true;
            }
        }
    }
}

线性筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 \(O(n)\) 了。

vector<int> pri;
bool not_prime[N];

void pre(int n)
{
	for (int i = 2; i <= n; ++i)
	{
		if (!not_prime[i])
		{
			pri.push_back(i);
		}
		for (int pri_j : pri)
		{
			if (i * pri_j > n)
				break;
			not_prime[i * pri_j] = true;
			if (i % pri_j == 0)
			{
				// i % pri_j == 0
				// 换言之，i 之前被 pri_j 筛过了
				// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break掉就好了
				break;
			}
		}
	}
}

例题

P1835 素数密度

首先结合上面推论，理论上只要利用不超过 \(\sqrt n\) 的质数就可以筛除 \(n\) 范围内的所有合数。

对于题目区间 \(2147483647\)，先预先求出 \(\sqrt {2147483647} = 50000\) 以内所有质数，再用这些质数对 \([L,R]\) 上的合数筛除即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e6 + 10;

using ll = long long;

bool is_prime[N];
bool no_prime[N];

int pri[10000];

int init()
{
	int cnt = 0;
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= 50000; ++i)
		is_prime[i] = true;
	for (int i = 2; i * i <= 50000; i++)
	{
		if (is_prime[i])
		{
			for (int j = i * i; j <= 50000; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
	for (int i = 2; i <= 50000; i++)
	{
		if (is_prime[i])
			pri[cnt++] = i;
	}
	return cnt;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int cnt = init();
	ll L, R;
	std::cin >> L >> R;
	for (int i = 0; i < cnt; i++)
	{
		for (ll j = std::max(2ll, (L - 1) / pri[i] + 1) * pri[i]; j <= R; j += pri[i])
		{
			no_prime[j - L] = true;
		}
	}
	int ans = 0;
	no_prime[1] = true;
	for (ll i = L; i <= R; i++)
	{
		if (!no_prime[i - L])
			ans++;
	}
	std::cout << ans;
	return 0;
}