luogu P2043 质因子分解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define ll long long
#define IL inline
#define clear(a) memset(a,0,sizeof a)
int n,maxx;
int num[maxn];
void divide(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
maxx=max(maxx,i);
while(x%i==0)x/=i,num[i]++;
}
}
if(x>0)maxx=max(maxx,x),num[x]++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
divide(i);
for(int i=2;i<=maxx;i++)
if(num[i])
printf("%d %d\n",i,num[i]);
return 0;
}
Processed:
0.012, SQL:
8
