质数和约数
质数
【例题】Prime Distance(poj2689)
这题L，R范围很大，但是L,R差值在可以接受的范围内。因为一个数n的质因子不会超过\sqrt{n}，所以我们考虑线筛预处理\sqrt{R}范围内所有的质数，在线筛的的同时标记L到R范围的合数。
如何标记：对每一个质数p，枚举一个倍数i，将i*p标记为合数。i的范围是\lfloor \frac{L}{p} \rfloor \leq i \leq \lfloor \frac{R}{p} \rfloor（因为L \leq i*p \leq R）。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int pri[50010],pr;
bool v[50010];
void get_prime(int n)
{
memset(v,true,sizeof(v));
pr=0;
for(int i=2;i<=n;i++)
{
if(v[i]) pri[++pr]=i;
for(int j=1;(j<=pr)&&(i*pri[j]<=n);j++)
{
v[i*pri[j]]=false;
if(i%pri[j]==0) break;
}
}
}
bool f[1000010];
int main()
{
int L,R;
get_prime(50000);
while(scanf("%d%d",&L,&R)!=EOF)
{
if(L==1) L=2;
memset(f,true,sizeof(f));
for(int i=1;i<=pr;i++)
{
int l=(L-1)/pri[i]+1;
int r=R/pri[i];
for(int j=l;j<=r;j++)
if(j>1)
f[j*pri[i]-L]=false;
}
int last=-1,maxx=-1,minn=2147483647,a,b,c,d;
for(int i=0;i<=R-L;i++)
{
if(f[i])
{
if(last==-1){last=i; continue;}
if(i-last<minn)
{
minn=i-last;
a=last+L,b=i+L;
}
if(i-last>maxx)
{
maxx=i-last;
c=last+L,d=i+L;
}
last=i;
}
}
if(maxx==-1) puts("There are no adjacent primes.");
else printf("%d,%d are closest, %d,%d are most distant.\n",a,b,c,d);
}
return 0;
}【例题】阶乘分解（传送门）
本题前提是阶乘，所以所有小于N的数都会出现，那么N!中质因子的个数就等于1N每个数的质因子个数之和。假设质数p，在1N中，至少包含一个质因子p（也就是分解质因数中有p^k(k\geq 1)）的数有\lfloor \frac{N}{p} \rfloor个（因为p在N范围内的倍数有这么多个），同理至少包含两个质因子p（也就是分解质因数中有p^k(k\geq 2)）的数有\lfloor \frac{N}{p^2} \rfloor个，那么对于每个质数p，N!中质因数p的个数为\sum_{k=1}^{p^k<=N}\lfloor \frac{N}{p^k} \rfloor(k<=\lfloor log_pN\rfloor)还是很快的
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int pri[1000010],pr;
bool v[1000010];
int n;
void get_prime()
{
memset(v,true,sizeof(v)); pr=0;
for(int i=2;i<=n;i++)
{
if(v[i]) pri[++pr]=i;
for(int j=1;(j<=pr)&&(i*pri[j]<=n);j++)
{
v[i*pri[j]]=false;
if(i%pri[j]==0) break;
}
}
}
int main()
{
scanf("%d",&n);
get_prime();
for(int i=1;i<=pr;i++)
{
printf("%d ",pri[i]);
ll p=(long long)pri[i],sum=0;
while(p<=n)
{
sum+=n/p;
p*=pri[i];
}
printf("%lld\n",sum);
}
return 0;
}约数
【例题】反素数ant（BZOJ1053）
这道题需要几个实用的引理和思维方式。
1、1N中最大的反素数，就是1N中约数最多的数中最小的那个
证明：因为约数最多的数中最小保证比他小的数约数都没有比他更多的，满足了他是“反素数”。且在比他大的数中约数个数最多都不会超过他，满足了“最大”。
思维方式：我们可以从反素数和最大两个特征去寻找这样的数，这同样可以用在其他类似的问题上。
2、1~N(n\leq 2*10^9)中任意的数的质因子不会超过10个，且所有的质因子的指数总和不会超过30
证明：把最小的11个质数乘起来都已经超过了2*10^9，且最小的质数2的31次方也已经大于。
思维方式：这个方法是常用的约数类问题突破口，抓住质因数比比较少且指数也比较少这一点可以通过搜索来组成一个数的约数。
3、反素数的必要条件是，他的质因子是连续的若干个最小的质因数，且指数单调递减
证明：反证法，如果存在一个反素数x的质因数分解中存在一项p^k（p>29），那么因为引理2所以他一定不被一个小于等于29的质数整除，设这个质数数为p’，所以设x'=x/p^k*p'^k（也就是把x里面的p^k替换成p'^k），这样所得的$x'xx