质数、约数-526互联

质数相关

一、算数基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积

写作：

\[ n=p_1^{c1}p_2^{c2}\dots p_m^{cm} \]

\[ =\prod_{i=1}^mp_i^{ci} \]

二、因数分布

若存在一个正整数 $ n $ 为合数，则存在一个数 $ k $ ,满足 $ 2 $ $ \le $ $k \le $ $ \sqrt{n} $ 且 $ k|n $

证明：

首先证明一个结论：

如果 $m_1 \times m_2=n$ ，那么，$ m_1 $ 和 $ m_2 $ 必定有一个大于 $\sqrt{n}$，一个小于 $ \sqrt{n} $ 。

假如我们在 $ 2-\sqrt{n}$ 没有找到 $ n $ 的因数，在 $ \sqrt{n}-n $ 中找到了因数 $ m_1 $ ,根据上面的结论，另一个因数 $ m_2 $ 肯定在 $ 2-\sqrt{n} $ 之间，与在 $ 2-\sqrt{n} $ 之间没有找到因数矛盾，命题获证。

三、素数筛

1.埃氏筛

原理：素数的倍数一定不是素数

code

for(int i=2;i<=n;++i)
  if(isprime[i]==1)
  {
  	for(int j=2*i;j<=n;j+=i)
  	  isprime[j]=0;
  }

埃氏筛的复杂度已经非常接近线性了，但是不能完全达到线性，因为它在筛的时候会有重复，比如说 $12$，它在被 $2$ 筛过之后，循环到 $3$ 的时候都会再重新筛一遍。

2.线性筛

针对上面的埃氏筛存在的问题，我们可以让每一个合数只被它的最小质因数筛掉。具体的，它通过 if(i%prime[j] == 0) break; 这一行来实现。

简单理解一下：i%prime[j] == 0 ，说明 $\mathrm{i}$ 有 $\mathrm{prime_j}$ 这个因子。如果再往后循环，$\mathrm{i \times prime_{j+1}}$ 这个数里有 $\mathrm{prime_j}$ 这个因子，那么 $\mathrm{prime_{j+1}}$ 就不是它的最小质因子了，所以 break。

code

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e7 + 5;
const int M = 1e8 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}

bool isprime[M];
int n,q,k;
int cnt,prime[N];

il int read()
{
	int f=0,s=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
	for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
	return f ? -s : s;
}

il void get_prime(int n)
{
	memset(isprime , 1 , sizeof isprime);
	isprime[1] = 0;
	for(re int i=2;i<=n;i++)
	{
		if(isprime[i]) prime[++cnt] = i;
		for(re int j=1;j<=cnt && i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]] = 0;
			if(i % prime[j] == 0) break;
		}
	}
}

signed main()
{
	n = read() , q = read();
	get_prime(n);
	while(q--) k = read() , cout << prime[k] << "\n";
	return 0;
}
}

四、一个正整数 $ n $ ,至多只有一个大于 $ \sqrt{n} $ 的质因子

证明：设 $ p,q≥ sqrt(n) $ ， $ p | n $ , $ q | n $ ,那么我们有 $ pq | n $ , $ pq > n $ , 很显然矛盾，命题获证。

约数

一、基础知识

带余除法

设 $ a $ , $ b $ 是两个整数，且 $ b \not= 0 $ ，如果存在整数 $ c $ ,则存在唯一的整数 $ q,r $ , 使得 $ a=qb+r (0\leq r < b)$ ，该式被
称为带余除法，并记 $ r=a\mod b $ 。

整除

定义

若整数 $n$ 除以整数 $d$ 的余数为 $0$ ，即 $d$ 能整除 $n$ ，则称 $d$ 是 $n$ 的约数，计为 $d\mid n$。

性质

若 $ a \mid b $ 且 $ a \mid c $ ，则 $ \forall x,y $ ，有 $ a \mid xb+yc $ 。

证明：

把 $b$ 和 $c$ 里的 $a$ 提出来乘法分配一下就行了。
设 $ b=an, c=am $ ，则 $ xb+yc=xan+yam=a(xn+ym) $ ，很明显 $ a \mid a(xn+ym) $ ，命题获证。

若 $ a \mid b , b \mid c $ ，则 $ a \mid c $ 。（传递性）
若 $ ma \mid mb (m \ne 0) $ ，则 $ a \mid b $ 。
若 $ a \mid b $ 且 $ b \mid a $ ，则 $ a=\pm b $ 。

二、算术基本定理的推论

对于唯一分解的正整数 $ n= p_1^{c_1}p_2\dots p_m^{c_m} $

其正约数集合可写作 $ { p_1^{c_1}p_2 \dots p_m^{b_m}}$，其中 $0 \le b_i \le c_i $

其正约数个数为：

\[(c_1+1)(c_2+1)……(c_m+1)=\prod_{i=1}^m(c_i+1) \]

证明一下：关于这个数 $n$ ，仅和质因子 $p_i$ 及其幂次方有关的因子有 $c_i+1$个($1,p_i,p_i^1,p_i^2\dots p_i^{c_i}$) ，根据乘法原理，正约数个数就是 $\prod_{i=1}^m(c_i+1)$。

然后我们可以线性筛出来(

思路

设 $a_i$ 记录 $i$ 的最小质因子的次数，$d_i$ 记录 $i$ 的约数个数。

若 $i$ 是质数，$a_i = 1,d_i=2$。

我们知道，每个合数 $n$ 都是被最小的质因子筛掉的。设 $p_j$ 是 $n$ 的最小质因子，那么 $n$ 会通过 $p_j \times i$ 被筛掉，这就产生两种情况：

1. 若 $i$ 能被 $p_j$ 整除，则 $p_j$ 一定也是 $i$ 的最小质因子①。$a_n = a_i + 1$。又因为 $d_i = (a_i+1)\times \dots , d_n = (a_n+1)\times \dots$ ，变化的只有第一项。
所以 a[n] = a[i]+1,d[n] = d[i]/a[n]*(a[n]+1)
1. 若 $i$ 不能被 $p_j$ 整除，则 $p_j$ 不是 $i$ 的最小质因子。所以 $n$ 质因数分解后的第一个质因子就不是 $i$ 分解后的第一个质因子了，而变成了 $p_j$ ，所以式子中加了一项。
所以 a[n] = 1,d[n] = d[i]*(1+1)

①：反证法证明，若 $i$ 的最小质因子不是 $p_j$ ，那么 $n = i \times p_j$ 的最小质因子肯定也不是 $p_j$ ，不满足每个合数都被最小质因子筛掉，故 $p_j$ 也是 $i$ 的最小质因子。

Code

int a[N]; //a[i]记录i的最小质因子的次数
int d[N]; //d[i]记录i的约数个数
int prime[N],cnt;
bool isprime[N];

il void get_d(int n)
{
	memset(isprime , 1 ,sizeof isprime);
	isprime[1]=0; d[1] = 1;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i]) 
		{
			prime[++cnt]=i;
			a[i] = 1 , d[i] = 2;
		}
		for(int j=1;j<=cnt && prime[j]*i <=n ;j++)
		{
			int m = i*prime[j];
			isprime[m]=0;
			if(i%prime[j] == 0) 
			{
				a[m] = a[i] + 1;
				d[m] = d[i]/a[m]*(a[m]+1);
				break;
			}
			else a[m] = 1 , d[m] = d[i]*2;
		}
	}
}

其所有约数和为：

\[(p_1^0+p_1^1+\dots +p_1^{c_i})\dots (p_m^0+p_m^1+\dots p_m^{c_m})= \prod_{i=1}^m(\sum_{j=0}^{c_i}(p_i)^j) \]

这个也能筛出来(

思路

设 $g_i$ 表示 $i$ 的最小质因子的 $1+p^1+p^2+\dots +p^k$，$f_i$ 记录 $i$ 的约数和。

若 $i$ 是质数，$g_i = f_i = i+1$。

还是类似的两种情况：

1. 若 $i$ 能被 $p_j$ 整除，则 $p_j$ 一定也是 $i$ 的最小质因子。$g_i = p_j^0 + p_j^1 + \dots +p_j^k$ ，$g_n = p_j^0 + p_j^1 + \dots + p_j^{k+1}$ ，我们不好维护 $k$ 。
  我们把 $g_n$ 的后 $k$ 项同时提出来一个 $p_j$ , $g_n$ 就变成了 $p_j^0 + p_j(p_j^0 + p_j^1 + \dots +p_j^k)$ ，我们发现括号里面就是 $g_i$ ，这样就巧妙地解决了问题。
所以 g[n] = g[i] * p[j] + 1 , f[n] = f[i] / g[i] * g[n]。
1. 若 $i$ 不能被 $p_j$ 整除，则 $p_j$ 不是 $i$ 的最小质因子。所以同样的式子中加了一项。
所以 g[n] = p[j] + 1,f[n] = f[i]*g[n]

Code

//g[i]表示i的最小质因子的1+p^1+...+p^k
int g[N], f[N];//f[i]表示i的约数和
int prime[N],cnt;
bool isprime[N];

il void get_f(int n)
{
	memset(isprime , 1 ,sizeof isprime);
	isprime[1]=0; g[1] = f[1] = 1;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i]) 
		{
			prime[++cnt]=i;
			g[i] = f[i] = i+1;
		}
		for(int j=1;j<=cnt && prime[j]*i <=n ;j++)
		{
			int m = i*prime[j];
			isprime[m]=0;
			if(i%prime[j] == 0) 
			{
				g[m] = g[i]*prime[j]+1;
				f[m] = f[i]/g[i]*g[m];
				break;
			}
			else g[m] = p[j]+1 , d[m] = f[i]*g[m];
		}
	}
}

对于一个合数 $ n^2 $ ，它的约数个数为：

\[\prod_{i=1}^m(c_i \times 2+1) \]

很好理解，因为 $n^2$ 中每个质因子的幂次都是 $n$ 的 $2$ 倍，所以就是 $c_i \times 2 + 1$ 。

三、求 $N$ 的正约数集合

试除法

因为约数成对出现(除了完全平方数的 $\sqrt{n}$单独出现)。

所以我们只需要扫描 $1-\sqrt{n}$,尝试能否整除 $n$ 即可，时间复杂度 $O(\sqrt{n})$

由试除法引出的推论：一个整数 $N$ 的约数个数上界为 $2\sqrt{n}$

倍数法

若想求 $1-N$ 以内所有数的约数个数 , 若用试除法，复杂度是 $O(n\sqrt{n})$ ，太高。为此我们用到倍数法：$1-n$中以 $d$ 为约数的数就是$d$的倍数 $d,2d,3d\dots \lfloor \frac{n}{d}\rfloor \times d$ ，用这个来求。

Code

vector <int> factor[500005];
  for(re int i=1;i<=n;i++)
  	for(re int j=1;j<=n/i;j++)
  		factor[i*j].push_back(i);
  for(re int i=1;i<=n;i++)
  {
  	for(re int j=0;j<factor[i].size();j++)            cout << factor[i][j] << "";
   	cout << "\n";
  }

时间复杂度为 $O(N+N/2+N/3+\dots N/N) = O(NlogN)$

由倍数法引出的推论：$1-N$ 的约数个数总和大约为 $NlogN$

四、最大公约数和最小公倍数

性质：

1. $a \times b = \gcd(a,b) \times \text{lcm}(a,b)$

证明：设 $a = p_1^{a_1}p_2\dots p_m^{a_m} , b= p_1^{b_1}p_2\dots p_m^{b_m} $

则 $a \times b = p_1^{a_1+b_1}p_2^{a_2+b_2}\dots p_m^{a_m+b_m}$

$=p_1^{\min(a_1,b_1)+\max(a_1,b_1)}p_2^{\min(a_2,b_2)+\max(a_2,b_2)} \dots p_m^{\min(a_m,b_m)+\max(a_m,b_m)}$

$ = \gcd(a,b) \times \text{lcm}(a,b)$

1. 若 $a \mid m $ 且 $b \mid m$ , 则 $\text{lcm}(a,b) \mid m$
$c_m \geq \text{max}(c_a,c_b)$ ，所以自然而然 $\text{lcm}(a,b) \mid m$
1. 若 $d \mid a $ 且 $d \mid b$ , 则 $d \mid \gcd(a,b)$
$c_d \leq \text{min}(c_a,c_b)$ ，所以自然而然 $d \mid \text{gcd}(a,b)$
1. 若 $a,b,m \in \mathbb{N}$ , 则 $\text{lcm}(ma,mb) = m \times \text{lcm}(a,b)$
1. 更相减损术：
$\forall a,b \in \mathbb{N}$ ，$a\geq b$ ，有 $\text{gcd}(a,b) = \text{gcd}(b,a-b) = \text{gcd}(a,a-b)$

证明：对于 $a,b$ 的任意公约数 $d$ ，$d \mid a, d\mid b$ ，根据整除性质1得，很容易构造 $x=1,y=-1$ ,得到 $d\mid (a-b)$ ，因此 $d$ 也是 $b,a-b$ 的约数。所以 $a,b$ 的公约数集合和 $b,a-b$ 的公约数集合相同，它们的最大公约数自然也相等。
1. 欧几里得算法：
  见数学(Ⅱ):同余相关