质数、约数和因数和欧拉函数

2020-07-20

质数

定理1:不超过N的质数大约有N/lnN个 1e6内大约有80000个质数 (78498)

欧拉筛:时间复杂度O(NloglogN)

void prime(int n)
{
	int vis[N],primes[N],cnt=0;
	for(int i=2;i<=n;i++) {
		if(!vis[i]) primes[cnt++]=i;
		int bei=2;
		while(i*bei<=n) {
			vis[i*bei]=true;
			bei++;
		}
	}
} 
void prime(int n)
{
	for(int i=2;i<=n;i++) {
		if(v[i]) continue;
		cout<<i<<'\n';
		for(int j=i;j<=n/i;j++) v[i*j]=true;
	}
} 

线性筛: 每个合数i*P只会被其最小质因子筛一次 ,总复杂度为O(N)

void prime(int n)
{
	int st[N],primes[N],cnt=0;
	for(int i=2;i<=n;i++) {
		if(!st[i]) primes[cnt++]=i;
		for(int j=0;i*primes[j]<=n;j++) {
			st[i*primes[j]]=true;
			if(i%primes[j]==0) break;//此时pirmes[j]是i的最小质因子 
		}
	}
} 

质因数分解:

  1. 试除法:O(根号N)
void divide(int n)
{
	int m=0;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0) {//分解因子 一定得到的是N=p1^c1*p2^c2.... p1、p2均为质数 
			int s=0;
			p[++m]=i,c[m]=0;
			while(n%i==0) n/=i,c[m]++;
		}
	}
	if(n>1) p[++m]=n,c[m]=1;//n为质数 
	for(int i=1;i<=m;i++) cout<<p[i]<<' '<<c[i]<<''
}

N!质因数分解:

#include<bits/stdc++.h>

using namespace std;

const int N=1e6;

int primes[N];
int cnt;
bool st[N];

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

int main()
{
	int n;
	cin>>n;
   	init(n);
	for(int i=0;i<cnt;i++) {
		int s=0;
		int p=primes[i];
		for(int j=n;j>=2;j/=p) s+=j/p;//  N/p即代表1-N中有多少数是p的倍数!!
		cout<<p<<' '<<s<<'\n';
	}
}

因子个数:

先分解质因子:N=p1^c1p2^ c2 *p3^c3...pk^ck

因子个数即为:(c1+1)(c2+1) (c3+1)(c4+1)...

/*
Keep clam  Believe youself
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<cmath>
#include<unordered_map>
#define Xiaobo main
using namespace std;
const int maxn=2e5+7;
const int mod=1e9+7;
const double eps=1e-15;
const double pi=acos(-1);
const int INF=0x3f3f3f;
typedef long long ll;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}
//别急 dp找状态 问题看看本身的规律 贪心找方法
int Xiaobo()
{
	int n;
	cin>>n;
	unordered_map<int,int>prims;
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		for(int i=2;i<=x/i;i++) {
			while(x%i==0) {
				x/=i;
				prims[i]++;
			}
		}
		if(x>1) prims[x]++;
	} 
	ll res=1;
	for(auto item:prims) {
		res=res*(item.second+1)%mod;
	}
	cout<<res<<'\n';
	return 0;
}

因子和:

(p1^0+p1^1+...+p1^c1)*(p2^0+p2^1+...+p2^c2)......

#include<bits/stdc++.h>

using namespace std;

unordered_map<int,int>primes;


int main()
{
	int x;
	cin>>x;
	int d=x; 
	for(int i=2;i<=d/i;i++) {
		int s=0;
		if(d%i==0) {
			while(d%i==0) d/=i,s++;
			primes[i]=s;
		}
	}
	if(d>1) primes[d]=1;
	int res=1;
	for(auto item:primes) {
		int a=item.first,b=item.second;
		int t=1;
		while(b--) t=(t*a+1);
		res*=t; 
	}
	cout<<res<<'\n';
	return 0;
}

求一个数的所有约数:

#include<bits/stdc++.h>

using namespace std;

const int N=50010;

int primes[N];
int cnt;
bool st[N];

struct st{
	int p,s;
}Factor[1610];
int fcnt;

int dividor[N],dcnt;

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

void dfs(int u,int p)
{
	if(u==fcnt) {
		dividor[dcnt++]=p;
		return ;
	}
	for(int i=0;i<=Factor[u].s;i++) 
	{

		dfs(u+1,p);
		p*=Factor[u].p;
	}
}
int main()
{
	init(N);
	int d;
	cin>>d;
	int t=d;
	fcnt=0;
	for(int i=0;primes[i]<=t/primes[i];i++) {
		int p=primes[i];
		int s=0;
		if(t%p==0) {
			while(t%p==0) s++,t/=p;
			Factor[fcnt++]={p,s};
		}
	} 
	if(t>1) Factor[fcnt++]={t,1};
//		cout<<'\n';
//		for(int i=0;i<fcnt;i++) {
//			cout<<"gg"<<' '<<Factor[i].p<<' '<<Factor[i].s<<'\n'; 
//		}
	dcnt=0;
	dfs(0,1);
	cout<<'\n';
	for(int i=0;i<dcnt;i++) cout<<"hh"<<' '<<dividor[i]<<'\n';
	return 0;
}
void init(int n) {
    cnt = 0;
    set<int>zc;
    for (int i = 1; i<=n/i; i++) {
        if (n % i == 0) {
        	zc.insert(i);
            if(i!=n/i) zc.insert(n/i);
        }
    }
    //zc.insert(n);
    for(auto item:zc) 
    {
    	factor[cnt++]=item;
    }
}

求1——N每个数的正约数集合——倍数法


void init(int n)
{
	vector<int>factor[500100];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n/i;j++)
			factor[i*j].push_back(i);
	for(int i=1;i<=n;i++) {
		for(int j=0;j<factor[i].size();j++)
			cout<<factor[i][j]<<' ';
		cout<<'\n'; 
	} 
}

线性筛求欧拉函数:欧拉函数:1-N中与N互质的数的个数:

void init(int n)
{
	phi[1]=1;
	for(int i=2;i<=n;i++) {
		if(!st[i]) {
			primes[cnt++]=i;
			phi[i]=i-1;//如果i为质数
		}
		for(int j=0;i*primes[j]<=n;j++) {
			st[i*primes[j]]=true;
			if(i%primes[j]==0) {
				phi[primes[j]*i]=phi[i]*primes[j];
				break;
			}
			phi[primes[j]*i]=phi[i]*(primes[j]-1);
		}
	}
}


标题:质数、约数和因数和欧拉函数
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/07/20/1595210134564.html