质因子分解 题解

题目链接:problem

题目本来就很清真,抄一下就行啦(doge :

对N!进行质因子分解。


这道题是一道水题,比某道大水题(我不说是谁)水100倍,

首先

枚举1~n进行分解质因数,计数一下,就做出了

(本程序已做防抄袭处理,包括但不限于变量名缺失、分号漏写······)

#include <iostream>
#define int long long
using namespace std ;
int n , m , f [1010] ;
void fj (int x) {
	for (i = 2 ; i <= sqrt (x) ; i ++)
		while (x % i == 0) {
			f [i] ++ ; 
			x /= i ;
		}
	if (x != 1)  f [x] ++ ;
}
main () {
	cin >> n ;
	for (i = 1 ; i <= n ; i ++)  fj (i) ;
	for (i = 1 ; i <= n ; i ++)
		if (f [i] != 0)  cout << i << " " << f [i] << "\n" 
	return 114514 ;
}

2 个赞

再加一个素数筛,可以做一点优化的。

1 个赞

可以