正文索引 [隐藏]

筛法

计算机中常使用筛法来计算素数。筛法的基本思想都是从一个区间中删去不符合要求的数，从而得到一个符合要求的区间，所以形象的称呼为筛法。

埃拉托斯特尼筛法(埃筛)

它又叫线性筛。埃筛可以快速获取小于等于n的素数集合。首先明确一点：对于任意合数x，它必有一个小于等于sqrt(x)的因子，因为如果两者均大于sqrt(x)那么其积必大于x。那么判断x是否为素数只需要判断2~sqrt(x)能否与x整除即可，如果一直计算到sqrt(x)都没有出现x的因数那x就是一个素数了。

埃筛基于以下原理：对于一个素数n(n>1)，它的k(k>1)倍数一定是一个合数。

假设要计算100以内的素数，从2开始遍历。

  1. 将2在100以内的所有倍数标记为合数。
  2. 指针后移，检查3是否为合数。3不是合数，那么把3的所有倍数也标记为合数。
  3. 指针后移，检查4是否为合数。4已经被标记为合数，跳过它。
  4. 重复上述流程一直到sqrt(100)。

事实上埃筛可以进行优化，即每次标记从大于等于自身的倍数开始进行。如5，只要标记5 × 5, 5 × 6, 5 × 7…为合数，因为5 × 2, 5 × 3, 5 × 4…已经被之前出现的数的倍数标记过了。

//时间复杂度O(sqrt(n))
void findPrimes(int n) 
{
	int p[n];
	p[0] = 0;//放个0占位
	int s = sqrt(n);
	for (int i = 2; i <= s; i++)//从2到sqrt(x)计算
	if (p[i] != 0) //如果i不是合数
	{
		int a = i * i;//从大于等于自身的倍数开始
		while (a <= n) 
		{
			p[a] = 0;//标记为合数
			a += i;//跳向下一个倍数
		}
	}
}

欧拉筛

埃筛的思想很好理解，但可能出现同一个合数被不同质因子重复筛去的可能。欧拉筛作为埃筛的优化版本，减去了这种冗余的计算，让每个合数只被它的最小质因子筛掉。所以他又叫快速线性筛。

void findPrimes(int n) 
{
    int cnt = 0;
	int b[n], p[n];//b[i]=1表示i为合数, p用来存素数集合 
    for (int i = 2; i <= n; i++)
	{
        if (!b[i])//判断并记录素数 
            p[++cnt] = i;
        for (int j = 1; j <= cnt && i*p[j] <= n; j++)//开始筛 
		{
            b[i*p[j]] = 1;//①
            if (i % p[j] == 0)  break;//②
        }
    }
}

①：此处i*p[j]表示将第一个素数到目前最后一个素数的i倍标记为合数。如果说传统埃筛是每步将一个素数的所有倍数标记，那欧拉筛就是每步将所有素数的一个倍数标记，结果相同方式不同，只是为了后续优化好计算做的改变。

②：此处就是欧拉筛的优化点。当i%p[j]==0时i是p[j]的倍数，即i=k × p[j]。此时的p[j]就是i的最小质因子。如果此时不break，继续去算i × p[j+1]，那么有等式i × p[j+1]=k × p[j] × p[j+1]。当i等于k × p[j+1]时就会重复计算。所以此处break可以避免重复筛同一个合数。

区间筛

区间筛针对的问题与埃筛和欧拉筛不尽相同。它针对的问题是： 给定整数 a 和 b，请问区间 [a,b) 内有多少个素数？

上文提到对于任意一个合数n，它必有一个小于等于sqrt(n)的因子。那么推广一下，对于在区间[a,b)的任意合数，它的最小质因子也一定不超过sqrt(b)。思路很明显了，为了筛到大区间[a,b)中的所有素数，可以先做[2,sqrt(b))这个小区间内的素数表，然后根据倍数筛去大区间内的合数即可。素数表由欧拉筛得到。

void sectionSieve(ll l,ll r)
{
	//f为小区间素数表，t为大区间素数表 
    for(ll i = 2; i*i < r; i++)
    {
        if(!f[i])
        {
            for(ll j = i*2; j*j < r; j += i) //i是素数，所以从2*i枚举小区间，j是l之后第一个i的倍数，故j+i也是i的倍数 
                f[j] = 1;
            for(ll j= (l+1)/i*i; j < r; j += i) //(l+1)/i 得到最接近l的i的倍数，最低是i的2倍，然后筛选
                t[j-l]=1;
        }   
	}  
}

最后t[l~r]中就是素数表。也可以用下标偏移来做优化。

一些题目

计蒜客A1956-SUM

题目大意：
如果一个整数不能被拆分成除1外的任何一个平方数，那么它被称为无平方因子数。举个例子：6(=2·3)就是一个无平方因子数，但12(=4·3)就不是，因为4(=2^2)是一个平方数。一些整数可以被拆分成两个无平方因子数之积(这种拆分可能不止一种)。举个例子：6=6·1=2·3=3·2=1·6。当a!=b时我们认为n=ab与n=ba是两种拆分。f(n)表示n的拆分方案数，请你计算sum[f(1~n)]。

输入：
第一行包含一个整数T(T<=20)，表示T组测试数据。
对任意一组数据，第一行包含一个整数n(n<=2e7)。

输出：
对任意一组数据，输出答案sum[f(1~n)]。

样例输入：
2
5
8
样例输出：
8
14

思路：
分析题目特性，可以得到以下规律。对任意的n有：

  • n=1时
    显然，f(1) = 1·1 = 1。
  • n是素数时
    对任意的素数，必然只有n = 1·n，所以此时f(n) = 2。
  • n = i · Pj时
    这个要分为两种情况讨论
    1. Pj^2|i 。因为Pj是一个素数，所以i至少等于Pj^2，那么n中至少含有三个Pj，不论怎么拆分都会产生平方因子。 此时f(n) = 0。
    2. 除上述情况之外，可以看做先拆i，i = a·b，那么n=(a·b)·Pj。所以此时f(n)=f(n/Pj)。

根据上述思路，先用欧拉筛预处理数据，然后直接查询。时间复杂度是O(n)+O(1)。

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

#define get(x) scanf("%d", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int  LIM = ll(2e7)+5;

int t, n, cnt;
int p[LIM], f[LIM];
bool vis[LIM];

void eulerSieve()
{
	vis[0] = vis[1] = 1;
	f[1] = 1;//n=1时只有一种 
	for (int i = 2; i < LIM; i++)
	{
		if(!vis[i])
		{
			p[++cnt] = i;
			f[i] = 2;//n是素数的情况 
		}
		for (int j = 1; j <= cnt && ll(i)*p[j] < LIM; j++)
		{
			vis[i*p[j]] = 1;
			if (i % p[j] == 0)
			{
				 f[i * p[j]] = (i / p[j] % p[j] == 0 ? 0 : f[i / p[j]]);
				 break;
			}
			else f[i * p[j]] = f[i] * f[p[j]];
		}
	}
	for (int i = 1; i < LIM; i++) f[i] += f[i-1];
}

int main()
{
	eulerSieve();
	get(t);
	while(t--)
	{
		get(n);
		printf("%d\n", f[n]);
	}
	return 0;
}

洛谷1835-素数密度

题目：
给定区间[L,R]，计算区间内素数个数。1<=L,R<=int，R-L<=1e6。

输入：
L与R。

输出：
一个整数表示[L,R]中的素数个数。

样例输入：
2 11
样例输出：
5

板子题，主要是找手感。

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

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

typedef long long ll;

const int LIM = 1000001;

ll l, r;
int cnt;
int f[LIM], t[LIM];

void init(ll l,ll r)
{
    for(ll i = 2; i*i < r; i++)
    {
        if(!f[i])
        {
            for(ll j = i*2; j*j < r; j += i)
                f[j] = 1;
            for(ll j= (l+1)/i*i; j < r; j += i) //i是素数，所以从2*i枚举。j是l之后第一个i的倍数，故j+i也是i的倍数
                t[j-l]=1;
        }   
	 }  
}

int main()
{
	lget(l);
	lget(r);
	init(l, r+1);
	for(ll i = l; i <= r; i++) if(!t[i-l]) cnt++;
	cout << cnt;
	return 0;
}