暴力最后一个点过不了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int prime[N];
void getprime(int n)
{
for (int i = 2; i <= n/i; i++)
{
if (n % i == 0)
{
int s = 0;
while (n % i == 0)
{
s++;
n /= i;
}
prime[i] += s;
}
}
if (n > 1)
prime[n] += 1;
}
int main()
{
int n;
cin >> n;
for (int i = 2; i <= n; i++)
{
getprime(i);
}
for(int i=2;i<=n;i++)
{
if(prime[i]!=0)
printf("%d %d\n",i,prime[i]);
}
return 0;
}
线性筛+阶乘计算 阶乘计算公式!!!!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,prime[1000005],cnt,st[1000005];
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(st[i]==0)
{
prime[cnt++]=i;
}
for(int j=0;prime[j]<=n/i;j++)
{
st[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
cin>>n;
get_prime(n);
for(int i=0;i<cnt;i++)
{
int ans=0,t=n;
while(t)
{
ans+=t/prime[i];
t/=prime[i];
}
if(ans)
cout<<prime[i]<<" "<<ans<<endl;
}
return 0;
}