小于n的​​平方根的n的因子数

Question

我想查找数字900的因子数小于其平方根的数。 例如：有27个因子是900，我想找到比900根更小的因子数，即30个是1,2,3,4,5,6,9,10,12,15,18,20 25。

我目前有这个程序，通过计算素数因子的数量找到因素的数量。例如：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个因子的数目。感谢您的帮助。

Answer 1

如果您有n个因子的数目，只需将整数除以2即可得到小于平方根的因子数。这是有效的，因为n小于sqrt（n）的每个因子d对应于大于sqrt（n）（即n/d）的因子，所以这些因子的数量将是总数的一半（除非n是完美平方，在这种情况下，sqrt（n）是一个额外因素）。但是，除以2的整数除了处理该角落情况。事实上，根据需要27/2 = 13。