前文链接

数学基础(1)

例题

POJ 2262. Goldbach’s Conjecture

题目链接

题目大意

验证$1e6$之内的数满足Goldbach’s Conjecturre

Goldbach’s Conjecture(哥德巴赫猜想): 任何大于4的整数都可以分拆为两个奇质数之和

解析

看做$n$次询问问题处理，先预处理出$1e6$内的质数，从3开始找到vis[n-a]==false的质数. 算法时间复杂度为$\mathcal{O}(N+\frac{n}{\ln n})$.

$1\sim n$之间的质数数量约为$\frac{n}{\ln n}$个

AC代码

#include <cstdio>
#include <cstring>

using namespace std;
const int N=1000005;
int n, primes[N], cnt=0;
bool vis[N];

void Lsieve(){
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<N; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=N/i; j++){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    Lsieve();
    while(scanf("%d", &n), n){
        int i=1;
        for(; i<cnt; ++i){
            int a=primes[i];
            if(!vis[n-a]) {printf("%d = %d + %dn", n, a, n-a); break;}
        }
        if(i==cnt) printf("Goldbach's conjecture is wrong.n");
    }   
    return 0;
}

CodeForces 776B. Sherlock and his girlfriend

题目链接

题目大意

给定一个序列$2,3,\dots ,n+1$，对这些点进行染色，如果点$a$是点$b$的质因子，那么$a$和$b$需要被染成不同颜色，求出完成这个要求需要最少的颜色数，以及输出一种可行的染色方案.

解析

可以证明，至多使用$2$种颜色可以完成染色需求，将序列$2\sim n+1$的数中质数分为一类，合数分为一类，将质数类染成红色，合数类染成蓝色即可完成需求.
考虑可以只用1种颜色即可完成需求的情况，显然如果序列中的数两两互质，则使用1种颜色即可完成需求，此时如果向序列中添加一个合数，使得其中一个质数成为该合数的质因子，那么就需要2种颜色. 因此，当$n\le 2$时，只要1种颜色.

AC代码

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

using namespace std;

const int N=100005;
int primes[N], n, cnt=0;
bool vis[N];

void Lsieve(){// 线性筛
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<=n; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    scanf("%d", &n);
    ++n;
    Lsieve();
    if(n<=3) printf("1n");
    else printf("2n");
    for(int i=2; i<=n; ++i){
        if(!vis[i]) printf("1 ");
        else printf("2 ");
    }
    return 0;
}

ACW 196/POJ 2689. 质数距离

题目链接

题目大意

给定两个整数$L$和$R$，其中$1\le L\le R\le 2^{31}$且$R-L\le 10^6$，求区间$[L,R]$中相邻两个质数差值最小的数对和差值最大的数对.

解析

如果直接使用线性质数筛筛出所有的质数，那么时间复杂度为$\mathcal{O}(n)$，考虑到$2^{3}1\approx 2.1e9$所以会TLE.
考虑到$R-L$是一个比较小的数，因此需要设计一种筛区间质数的算法，考虑可以筛出$x$的质因子最大值不会超过$\sqrt{x}$，分两步筛选：

1. 筛出$2\sim \sqrt{R}$中所有的质数，设质数集合为$\mathbb{P}$
2. 对于每个$p\in \mathbb{P}$，标记$[L,R]$中所有能被$p$整数的数.

算法时间复杂度为$\mathcal{O}(\sqrt{R}\ln \ln \sqrt{R}+(R-L)\log \log R)$

AC代码

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

const int N=1000005;
typedef long long LL;
int primes[N], n, cnt=0;
bool vis[N];
int l, r;

void Lsieve(int n){ // 线性筛
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<=n; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    Lsieve(50000);
    while(cin>>l>>r){
        memset(vis, 0x00, sizeof vis);
        for(int i=0; i<cnt; ++i){
            LL p=primes[i];
            for(LL j=max(2*p, (l+p-1)/p*p); j<=r; j+=p) vis[j-l]=true;
        }
        int knt=0;
        int sub[r-l+1];
        memset(sub, 0x00, sizeof sub);
        for(int i=0; i<=r-l; ++i){
            if(!vis[i] && i+l>1) sub[knt++]=i+l;
        }
        if(knt<2) cout<<"There are no adjacent primes."<<endl;
        else{
            int minp=0, maxp=0; // 存储下标
            for(int i=0; i+1<knt; ++i){
                int d=sub[i+1]-sub[i];
                if(d<sub[minp+1]-sub[minp]) minp=i;
                if(d>sub[maxp+1]-sub[maxp]) maxp=i;
            }
            printf("%d,%d are closest, %d,%d are most distant.n", sub[minp], sub[minp+1], sub[maxp], sub[maxp+1]);
        }
    }
    
    return 0;
}

ACW 197. 阶乘分解

题目链接

题目大意

给定整数$n$，将$n!$分解质因数

解析

由算术基本定理

任何大于1的正整数都可以唯一分解为有限个质数的乘积，$N=p_1^{c_1}{p}_2^{c_2}\dots p_m^{c_m}$，其中$c_i$是正整数，$p_i$是质数且满足$p_1<p_2<\cdots <p_m$.

扫描$2\sim \sqrt{N}$中每个质数$d$，如果$d\mid N$，则一直执行N/=d运算直到$d\nmid N$，如果最后余下的值不为1，那么也是$N$的质因子，一并加入结果. 算法时间复杂度为$\mathcal{O}(\sqrt{N})$.
算法模板代码如下

void divide(int n){
	int k=0;
	for(int i=2; i<=n/i; ++i){
		if(n%i==0){
			p[k++]=i; c[k]=0; // 记录分解的质因子和其指数
			while(n%i==0) {n/=i; c[k]++;}
		}
	}
	if(n>1){p[++k]=m; c[k]=1;}
}

本题中给出的$N$达到$1e6$级别，因此按照常规思路逐一分解后累计的方法时间复杂度为$\mathcal{O}(n\sqrt{n})$，会TLE.
不妨从质因子的角度去考虑该问题，对$2\sim n-1$所有的质因子进行枚举，一次统计$p,p^2,\dots ,p^k$贡献的次数，分别为$\lfloor \frac{n}{p}\rfloor ,\lfloor \frac{n}{p^2}\rfloor ,\dots ,\lfloor \frac{n}{p^k}\rfloor$个，所以$p$的指数$I$表达式为
$$I=\sum _{i=1}^k\lfloor \frac{n}{p^i}\rfloor$$
算法时间复杂度为$\mathcal{O}(\frac{n}{logn}\ast logn)=\mathcal{O}(n)$

AC代码

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

using namespace std;
const int N=1000005;
int primes[N], cnt=0;
bool vis[N];

void Lsieve(int n){
    for(int i=2; i<=n; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    int n;
    cin>>n;
    Lsieve(n);
    for(int i=0; i<cnt; ++i){
        int p=primes[i];
        int k=0;
        for(int j=n; j; j/=p) k+=j/p;
        cout<<p<<" "<<k<<endl;
    }
    return 0;
}

最后

以上就是眼睛大柜子为你收集整理的【ALGO】数论算法(2) 质数筛例题前文链接例题的全部内容，希望文章能够帮你解决【ALGO】数论算法(2) 质数筛例题前文链接例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。