算法分析

• 1、筛出1~10^6的所有质数
• 2、枚举每个质因子P，n!表示1 * 2 * 3... * n,从1到n中，求P的次数：$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor …$(一共有$log_{p}n$项)
  • P的倍数有$\lfloor \frac{n}{p} \rfloor$个
  • P^2的倍数有$\lfloor \frac{n}{p^2} \rfloor$个
  • P^3的倍数有$\lfloor \frac{n}{p^3} \rfloor$个
  • …

时间复杂度 $O(n)$

有$\frac{n}{lnn}$个质数，每个质数求$log_{p}n$次，因此时间复杂度是$O(n)$级别

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 1000010; 
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];
    static int cnt = 0;
    static void init(int n)
    {
        for(int i = 2;i <= n;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        init(n);
        for(int i = 0;i < cnt;i ++)
        {
            int p = primes[i],s = 0;
            for(int j = n;j != 0;j /= p)
            {
                s += j / p;
            }
            System.out.println(p + " " + s);
        }
    }
}