AcWing 179. Factorial decomposition problem solution

AcWing 197. Factorial decomposition Answer key

Better reading experience

Title Description

Given integer $N$ , Try factorial $N!$ Decomposing prime factor , According to the form of the basic theorem of arithmetic, output the $p_i$ and $c_i$ that will do

Input format

An integer $N$

Output format

$N!$ The result of decomposing the prime factor , There are several lines , Each row of a pair of $p_i,c_i$ , Means to contain $p_i^{c_I}$ term . according to $p_i$ Sequential output from small to large

Data range

$3\le N\le 10^6$

Answer key

about $N!$ The quality factor of , We can judge , The maximum quality factor does not exceed $N$

prove ：

Through the basic theorem of arithmetic

For any positive integer, there are
$$x=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot p_3^{{\alpha }_3}\dots \cdot p_n^{{\alpha }_n}$$
among $P_i$ by $x$ The quality factor of

about $1$ ~ $N$ Each integer of can be decomposed into the form of basic theorem of arithmetic

therefore $N!$ The basic theorem of arithmetic is the former $N$ The product of the basic arithmetic theorem of numbers , There is no more than $N$ The quality factor of

Obtain evidence

So we just need to sift out $1$~ $N$ The prime number of

First, use the linear sieve to screen out the prime numbers

 public static void init(int n)
    {
    
        Arrays.fill(isPrime,true);
        for(int i=2;i<=n;i++)
        {
    
            if(isPrime[i])
                Primes[cnt++]=i;
            for(int j=0;j<cnt;j++)
            {
    
                int p=Primes[j];
                if(p*i>n)
                    break;
                isPrime[p*i]=false;
                if(i%p==0)
                    break;
            }
        }
    }

After sifting the prime number

We calculate the order of each prime

Computation $1$ ~ $N$ How many numbers in have prime numbers $p$

Easy to get $N/P$ Numbers have prime numbers p, These numbers are p Multiple , So these numbers have factors $p$

According to $N/P^2$ The number contains factors $p^2$

By analogy , We can calculate when $N/P^k$ When is 0, Prime number $P$ The corresponding maximum order is $k$

The code for calculating the order is as follows

 for(int i=0;i<cnt;i++)
        {
    
            int res=0;
            int p=Primes[i];
            int tmp=n;
            while(tmp>0)
            {
    
                res+=tmp/p;
                tmp/=p;
            }
            System.out.println(Primes[i]+" "+res);
        }

Complete code

import java.io.*;
import java.util.*;

public class Main{
    
    static int n;
    static final int N=(int)1e6+10;
    static boolean[] isPrime=new boolean[N];
    static int[] Primes=new int[N];
    static int cnt=0;
    public static void  init(int n)
    {
    
        Arrays.fill(isPrime,true);
        for(int i=2;i<=n;i++)
        {
    
            if(isPrime[i])
                Primes[cnt++]=i;
            for(int j=0;j<cnt;j++)
            {
    
                int p=Primes[j];
                if(p*i>n)
                    break;
                isPrime[p*i]=false;
                if(i%p==0)
                    break;
            }
        }
    }
    public static void main(String[] agrs) throws IOException
    {
    
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine());
        init(n);
        for(int i=0;i<cnt;i++)
        {
    
            int res=0;
            int p=Primes[i];
            int tmp=n;
            while(tmp>0)
            {
    
                res+=tmp/p;
                tmp/=p;
            }
            System.out.println(Primes[i]+" "+res);
        }
    }
}