Число факторов 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, чтобы получить количество факторов меньше квадратного корня. Это работает, потому что каждый коэффициент d n меньше, чем sqrt (n), соответствует коэффициенту, превышающему sqrt (n) (а именно n/d), поэтому число таких факторов будет составлять половину общего (если n не является идеальным квадратом, в этом случае sqrt (n) является дополнительным фактором). Однако целочисленное деление на 2 позаботится об этом краевом случае. Действительно, 27/2 = 13 по желанию.