代码之家  ›  专栏  ›  技术社区  ›  KCK

小于n平方根的n因子数

  •  2
  • KCK  · 技术社区  · 9 年前

    我想找出一个数的因子数,比如900,小于它的平方根。

    我现在有一个程序,通过计算素因子的数量来计算因子的数量。例如:140的素因子是:2^2*5*7。所以因子的个数是:(2+1)(1+1)(1+1)[素因子的幂乘法]

    import java.io.*;
    import java.util.*;
    class Solution
    {
    // Program to print all prime factors
    static void primeFactors(int n)
    {
    
        TreeMap tm=new TreeMap();
        int times=0;
        // Print the number of 2s that divide n
        while (n%2 == 0)
        {
            System.out.println("2");
            if(!tm.containsKey(2))
            {
                tm.put(2,1);
            }
            else
            {
                times=(int)tm.get(2);
                tm.put(2,times+1);
            }
            n = n/2;
        }
    
        // n must be odd at this point.  So we can skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i = i+2)
        {
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
                System.out.println(i);
                if(!tm.containsKey(i))
                {
                    tm.put(i,1);
                }
                else
                {
                times=(int)tm.get(i);
                tm.put(i,times+1);
                }
                n = n/i;
            }
        }
    
        // This condition is to handle the case whien n is a prime number
        // greater than 2
        if (n > 2)
        {
            System.out.println(n);
            if(!tm.containsKey(n))
            {
                tm.put(n,1);
            }
            else
            {
            times=(int)tm.get(n);
            tm.put(n,times+1);
            }
        }
    
        /////////////////////////////////////////////////////////////////////////////
        Set set = tm.entrySet();
        System.out.println(tm);
        Iterator num = set.iterator();
        int key=0;
        int sum=1;
        while (num.hasNext())
        {
            Map.Entry number =(Map.Entry)num.next();
            sum=sum*((int)number.getValue()+1);
        }
        System.out.println(sum);
    }
    
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        primeFactors(n);
    }
    }
    

    这里我得到了因子的数量,例如:27个因子代表900个因子,但我想找出小于30个因子的数量。谢谢你的帮助。

    1 回复  |  直到 9 年前
        1
  •  3
  •   bpachev    9 年前

    如果你有n个因子,简单地用整数除以2,得到小于平方根的因子数。这是因为n小于sqrt(n)的每一个因子d对应一个大于sqert(n)(即n/d)的因子,所以这类因子的数量将是总数的一半(除非n是一个完全平方,在这种情况下,sqrt是一个额外的因子)。然而,整数除以2就解决了这种情况。事实上,27/2=13是理想的。