文章

25

粉丝

0

获赞

0

访问

68438

头像
阶乘分解-(素数线性筛)
经验总结
发布于2020年4月18日 22:57
阅读数 2707

①先筛选出1~N的每个质数p
②N!中质因子p的个数为:
floor(N/p)+floor(N/p2)+floor(N/p3)+…+floor(N/pfloor(logpN))=Σ(pk≤N)floor(N/pk)

时间复杂度:O(NlogN)

N! 分解质因数后的结果,共若干行,每行一对pi​,ci​。按照pi从小到大的顺序输出。

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1000000 + 10; 
int prime[N];
int n, m;
void primes(int n){
	for (int i = 2; i <= n; i++){
		if (!prime[i]){ prime[++prime[0]] = i; }

		for (int j = 1; j <= prime[0] && i*prime[j] <= n; j++){
			prime[i*prime[j]] = 1;
			if (i%prime[j] == 0){ break; }
		}
	}
}

int main(){
	cin >> n;
	primes(n);
	/*for (int i = 0; i <= prime[0]; i++){
		cout << prime[i] << " ";
	}
	cout << endl;
	*/
	for (int i = 1; i <= prime[0]; i++){
		int p = prime[i];
		int t = 0;
		for (int j = 1; pow(p, j) <= n; j++){
			t += n / pow(p, j);
		}
		cout << p << " " << t << endl;
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发