题目
题解思路
一开始想枚举每一个数然后试除出质因子,这样复杂度N根号N 10的9次方 不行的。
闫总提供了一个一个在连续乘积中求质因子个数的快速方法。
直接除这个质因子,留下了的数就是有这个质因子的数的个数,剩下的继续除就是有2次方的数的个数,以此类推。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10 ;
int pre[N] ;
int prm[N] ;
int cnt = 0 ;
void in( int n )
{
pre[1] = 1 ;
for (int i = 2 ; i <= n ; i++ )
{
if ( ! pre[i] )
{
prm[cnt] = i ;
cnt++;
for (int j = i*2 ; j <= n ; j+=i )
pre[j] = 1 ;
}
}
}
int main ()
{
ios::sync_with_stdio(false);
int n ;
cin>>n;
in(n);
for (int i = 0 ; i < cnt ; i++ )
{
int p = prm[i] ;
int s = 0 ;
for (int j = n ; j > 0 ; j /= p )
s += j/p ;
cout<<p<<" "<<s<<"\n";
}
return 0 ;
}