小於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。