一个数只能被 1 1 1 和它本身整除，则为质数.
质数的基本性质- 0 , 1 0,1 0,1既不是质数也不是合数.
- 2 2 2 是最小的质数.
时间复杂度
O
(
N
)
O(sqrt N)
O(N
)
原理：埃氏筛法，正整数
n
n
n 是素数，当且仅当它不能被任何一个小于等于
n
sqrt n
n
的素数整除.
所以判定时，先特判
0
,
1
0,1
0,1 ，然后扫
2
−
n
2-sqrt n
2−n
bool check(int x)
{
int i;
if(x<2) return false;
rep(i,2,x/i) if(x%i==0) return false;
return true;
}
分解质因数
原理： n n n 中最多包含一个大于 n sqrt n n 的质因子，最后别忘记特判 n > 1 n>1 n>1 的情况.
void getfactor(int x)
{
int i,nums;
for(i=2;i<=x/i;++i)
{
if(x%i==0)
{
nums=0;
while(x%i==0) ++nums,x/=i;
printf("%d %dn",i,nums);
}
}
if(x>1) printf("%d %dn",x,1);
puts("");
}
线性筛质数模板
线性筛高效的原因：一个数只会被它最小的质因子筛掉
const int N=1e6+10;
int n,cnt;
int primes[N];
bool st[N];
void getprimes()
{
int i,j;
rep(i,2,n)
{
if(!st[i]) primes[cnt++]=i;
for(j=0;primes[j]<=n/i;++j)
{
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
二次筛法
概念：要筛的数太大，不可能从 1 1 1 开始筛，因此要先筛根号范围.
首先引入一个重要性质：
若一个数
x
x
x 是合数，则必然存在两个因子
d
d
d，
n
d
frac{n}{d}
dn，则必然存在一个小于等于
n
sqrt n
n
的因子.
问题背景：如何筛出 [ L , R ] [L,R] [L,R] 之间的质数，其中 R − L ≤ 1 0 6 R-Lle 10^6 R−L≤106.
具体步骤如下：
- 首先筛出 int 范围内的所有质数.
- 然后就是求出 [ L , R ] [L,R] [L,R] 种最小的 p p p 的倍数，即 ⌈ L p ⌉ p lceil frac{L}{p}rceil p ⌈pL⌉p
- 关键结论，即上取整转化为下取整的操作，即 ⌈ L p ⌉ = ⌊ L + p − 1 p ⌋ lceilfrac{L}{p}rceil=lfloorfrac{L+p-1}{p}rfloor ⌈pL⌉=⌊pL+p−1⌋
- 要注意特判 L = 1 L=1 L=1 的特殊情况.
对于任何正整数
x
x
x，其约数的个数记作
g
(
x
)
g(x)
g(x)
如果某个正整数
x
x
x 满足：对于任意的小于
x
x
x 的正整数
i
i
i，都有
g
(
x
)
>
g
(
i
)
g(x)>g(i)
g(x)>g(i)，则称
x
x
x 为反素数
如何求反质数？ 用搜索.
反质数的充要条件作为搜索的目标。
反质数的必要条件作为搜索的剪枝的依据。
充要条件：即为反质数的定义。
必要条件1：一个反素数的所有质因子必然是从2开始的连续若干个质数。
必要条件2：若
n
n
n 是反质数，且
n
=
2
p
1
∗
3
p
2
∗
5
p
3
∗
7
p
4
∗
.
.
.
.
n=2^{p_1}*3^{p_2}*5^{p_3}*7^{p_4}*....
n=2p1∗3p2∗5p3∗7p4∗....，则
p
1
≥
p
2
≥
p
3
≥
p
4
≥
.
.
.
.
p_1ge p_2ge p_3ge p_4ge ....
p1≥p2≥p3≥p4≥....
求不超过 N N N 的最大反素数
ll n,ans,nums;
ll primes[10]={2,3,5,7,11,13,17,19,23,29};
void dfs(int i,ll now_ans,ll now_nums,ll last)
{
if(now_nums>nums||(now_nums==nums&&now_ans
++k;
now_ans*=primes[i];
if(k>last||now_ans>n) return;
dfs(i+1,now_ans,now_nums*(k+1),k);
}
}
int main()
{
int i,j;
scanf("%lld",&n);
dfs(0,1,1,0x3f3f3f3f);
printf("%lld",ans);
return 0;
}
暑期编程PK赛
得CSDN机械键盘等精美礼品！
