[day 29] given an integer, please find its factor number

This article has been included in the column 《Java Introduction 100 cases 》

order 、 Column Preface

   This column opens , The purpose is to help everyone better master learning Java, Especially some Java Learners' It is difficult to find systematic algorithm learning materials on the Internet to help you get started with algorithms , At the same time, if you have any questions about the contents of the column, you can add my wechat at the end of the article to give you a one-to-one explanation .
   But the most important thing is to think independently , For all the content of this column , Be able to fully master , Write the code completely by yourself , There must be no problem getting started with the algorithm .
   The learning of algorithm must not be short of summary , Here I recommend that you can go to University algorithm community Punch in the learned knowledge , To consolidate and review .
   The only way to learn algorithms well must be Topic sea strategy , Only by accumulating a lot of practice can you practice your skills . Any topic of the column I will start with 【 Title Description 】【 Their thinking 】【 Template code 】【 Code parsing 】 Wait for four plates to explain .

One 、【 Example 1】

1、 Title Description

   Given an integer $n(1\le n\le 100000)$, Please find out the number of factors .

2、 Their thinking

• $(1)$ We can think of the previous articles on judging prime numbers , Because the determination of prime number also depends on the factor number of a number , It was written at that time $O(n)$ And a $O(\sqrt{n})$ How to do it .

3、 Template code

1.O(n) practice

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
    
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ans=0;
        for (int i = 1; i <=n; i++) {
    
            if (n%i==0) ans++;
        }
        System.out.println(ans);
    }
}

2. Radical sign n practice

import java.util.*;
public class Main {
    
    public static void main(String[] args) {
    
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ans=0;
        for (int i = 1; i <=n/i; i++) {
    
            if (n%i==0){
    
                if (i!=n/i) ans+=2;
                else ans++;
            }
        }
        System.out.println(ans);
    }
}

3. Theorem of the number of approximations

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
    
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(getsum(n));
    }
    static int getsum(int n){
    
        int ans=1;
        for (int i = 2; i <=n/i; i++) {
    
            if (n%i==0){
    
                int a=0;
                while (n%i==0){
    
                    a++;
                    n/=i;
                }
                ans*=(a+1);
            }
        }
        if (n>1) ans*=2;
        return ans;
    }
}

4、 Code parsing

• $(1)$ The first two methods are not mentioned here , In the $5$ It is explained in the prime number determination of days , Let's focus on the theorem of approximate numbers .
• $(2)$ For a greater than $1$ The integer of $n$, Decomposable prime factor
  $$n=\prod _{i=1}^k{p}_i^{a^i}=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k}$$
  be $n$ The positive divisors of are $f(n)={\prod }_{i=1}^k(a_i+1)=(a_1+1)(a_2+1)...(a_k+1).$
  among $a_1、a_2、a_3...a_k$ yes $p_1、p_2、p_3、...p_k$ The index of .
• $(3)$ Theorem proving ： about $n$, We have ：$n=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k}$
  about $n$ Any divisor of $d$, Then there are $d=p_1^{{}^{\beta }1}\times p_2^{{\beta }^2}\times p_3^{{\beta }^3}......p_k^{{\beta }^k}$, among $(0\le {\beta }_i\le a_i)$, every last ${\beta }_i$ The value of is in total $(a_i+1)individual$. Of each item ${\beta }_i$ Different , Then the divisors are different .${\beta }_1$ The range is $[0,a_1]$,${\beta }_2$ The range is $[0,a_i]$,${\beta }_k$ The de value range of is $[0,a_k]$.
• $(4)$ According to the principle of multiplication ,$n$ The approximate number of $f(n)=(a_1+1)(a_2+1)...(a_k+1)$
  

3、 ... and 、 Recommendation column

《 Zero fundamental algorithm 100 God 》

Four 、 After-school exercises

Serial number	Topic link	Difficulty rating
1	Ugly number	2

There are questions about learning ？