import java.util.*;
public class Main {
static int cnt=0;
static int N=(1 << 20) + 10;
static boolean[] st=new boolean[N];
static int[] primes=new int[N];
static int[] pmin=new int[N];
static void get_primes(int n) {
for(int i=2;i<=n;i) {
if(!st[i]) {
primes[cnt]=i;
pmin[i]=i;
}
for(int j=1;primes[j]i<=n;++j) {
int t=primes[j]i;
st[t]=true;
pmin[t]=primes[j];
if(i%primes[j]==0) break;
}
}
}
static int[] sum=new int[N];
public static void main(String[] args) {
get_primes(N-1);
Scanner sc=new Scanner(System.in);
int n;
while(sc.hasNextInt()) {
n=sc.nextInt();
int k=0,tol=0;
while(n>1) {
int p=pmin[n];
sum[k]=0;
while(n%p==0) {
tol++;
n/=p;
sum[k]++;
}
k++;
}
long res=1;
for(int i=1;i<=tol;++i) {
res*=i;
}
for(int i=0;i<k;++i) {
for(int j=1;j<=sum[i];++j) {
res/=j;
}
}
System.out.println(tol+" "+res);
}
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla