素数

判定：

可以 \(O(\sqrt n)\) 复杂度暴力的求出一个数是否是素数。

筛选：

埃式筛法：

扫描每个没有被打标记的数，将它的倍数打上标记，剩余的所有没有打标记的就是素数。

线性筛法：

扫描每个数，如果没有被打标记，那么把这个数压入素数表里，然后把这个数的标记打为自己，之后对每个数，把所有比他的标记小的素数和他自己相乘，把新的这个数打上乘的那个素数的标记。这样，我们保证所有的数都只会被它最小的质因数给筛一遍。

注意：这里的标记和上面的标记不同，上面埃式筛法的标记指的是是否扫描过，这里指的是当前数字的最小质因数。

例题：luoguP1865

首先我们看到 \(m\) 值域的范围较小，我们考虑先预处理出所有位置到1的前缀素数个数和，然后每次询问通过查询前缀和之差得到 \(l\sim r\) 范围内的质数个数，筛法就用线性筛，套板子就可以了。

Code：

#include <iostream>
#include <cstdio>
using namespace std ;

const int N = 10000005 ;
int n , m , c , p[N] , vis[N] , cnt[N] ;

int main ( )
{
	cin >> n >> m ;
	for ( int i = 2 ; i <= m ; ++ i )
	{
		if ( ! vis [ i ] )
		{
			++ c ;
			p [ c ] = i ;
			vis [ i ] = i ;
			++ cnt [ i ] ;
		}
		for ( int j = 1 ; j <= c ; ++ j )
		{
			if ( p [ j ] > vis [ i ] )
				break ;
			if ( i > m / p [ j ] )
				break ;
			vis [ i * p [ j ] ] = p [ j ] ;
		}
		cnt [ i ] += cnt [ i - 1 ] ;
	}
	for ( int i = 1 ; i <= n ; ++ i )
	{
		int l , r ;
		cin >> l >> r ;
		if ( l < 1 || r > m || r < l )
		{
			puts ( "Crossing the line" ) ;
			continue ;
		}
		cout << cnt [ r ] - cnt [ l - 1 ] << endl ;
	}
	return 0 ;
}

反素数

如果某个正整数满足所有小于这个数的约数个数都小于它的约数个数，那么称这个数为反素数。

如果把一个数写成： \(a~=~p_1^{k_1}~p_2^{k_2}~\cdots ~p_n^{k_n}\)

引理：

• 反素数肯定是从2开始的连续素数的幂次方
• 数值小的素数的幂次大于等于数值小的素数的，即：\(k_i<k_2<\cdots <k_n\)

如果第一条不满足，那么一定可以找到一个更小的素数代替某个素数因子的位置，所以这个数就不可能是反素数。

如果第二条不满足，那么我们一定可以找到两个位置交换他们的指数，这样这个数的总因子个数不变，但是数字变小了，所以之前的那个数一定也不是反素数。

所以如果我们要求1到某个数值的反素数，我们可以基于上面这些定理进行搜索。

例题：luoguP1463 HAOI2007 反素数

题目大意是：求出比给定的n小的最大的反素数。

数据范围： \(1\le n \le 2\times 10^9\)

解法：

我们考虑搜索，因为 \(n\)小于等于 \(2e9\)，经过用计算器的计算我们的得出最多有 \(9\) 个不同的质因子，原因是因为 \(2\times 3\times 5\times \cdots \times 29\) 是大概 \(6e9\) 左右，已经大于 \(2e9\) 的数据范围了，所以最多有九个（到 \(23\)，\(29\) 是第十个），如果不放心可以枚举到第十一个。

然后每个质因数的指数最大是 \(31\)，因为 \(2\) 的 \(32\) 次方大于 \(2e9\) （常识，然后我们遵循上面两条的原则进行搜索。

1.当当前值大于 \(n\) 的时候，返回；

2.当当前枚举到的质数的指数大于上一个的时候，返回；

3.当前枚举到第十（一）个质数或者指数为 \(31\) 的时候，返回。

然后对每次搜索得到的数和答案取 \(max\)，最后输出一下就可以了。

Code：

#include <iostream>
using namespace std ;

int d[12] = { 1 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 } ;
int n , ans ;
long long res ;

//y当前枚举质因子位置 z质因子指数总数 p前一个质因子指数 
void dfs ( long long x , int y , int z , int q ,  int p )
{
	if ( y > 10 )
		return ;
	if ( q > 30 )
		return ;
	if ( x > n )
		return ;
	if ( z > ans )
	{
		ans = z ;
		res = x ;
	}
	if ( z == ans && x < res )
		res = x ;
	for ( int i = 1 ; i <= p ; ++ i )
	{
		x *= d [ y ] ;
		dfs ( x , y + 1 , z * ( i + 1 ) , q + i , i ) ;
	}
}

int main ( )
{
	cin >> n ;
	dfs ( 1 , 1 , 1 , 0 , 30 ) ;
	cout << res << endl ;
	return 0 ;
}

整理

最后，整理一下对于做素数的题的思路：

如果发现值域较大，那么首先先用线性筛法筛出来范围内的素数，或者用一定的手段，比如用 \(\log n\) 的范围筛出来 \(1-n\) 的素数。

如果值域较小或者具有特定性质使用到的质数不会很多的话，可以通过预先达标来解决。

然后看一下接下来的题目大意，如果要求一段区间里的素数个数或者第 \(k\) 小的素数，可以考虑用数据结构去维护，如果要求一个最大值或者最小值或者因子最多的这样子的数，可以用反素数的知识，通过搜索得到答案。

欧拉函数

欧拉函数表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。

例如： \(\varphi(1) ~= ~1\)

当 \(n\) 是素数的时候，显然有 \(\varphi(n) ~= ~n - 1\)

性质：

• 欧拉函数是积性函数

  即： \(gcd(a,b)=1\Rightarrow \varphi(a\times b) = \varphi(a) \times \varphi(b)\)

• \[n = \Sigma_{d|n}~\varphi(d) \]

  可以用莫比乌斯反演得出（但我不会

• \[n = p^k, ~且 p 是质数 ~\Rightarrow \varphi(n) = p^k - p^{k-1} \]

  根据定义可得。