количество множителей n, которые меньше квадратного корня из n

Я хочу найти количество множителей числа, скажем, 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. Спасибо за помощь.


person KCK    schedule 06.08.2016    source источник


Ответы (1)


Если у вас есть число множителей n, просто разделите целое число на 2, чтобы получить число множителей меньше квадратного корня. Это работает, потому что каждый множитель d числа n меньше, чем sqrt(n), соответствует фактору, большему, чем sqrt(n) (а именно, n/d), поэтому количество таких множителей будет вдвое меньше (если только n не является полным квадратом, в этом случае sqrt(n) является дополнительным фактором). Однако целочисленное деление на 2 решает этот угловой случай. Действительно, 27/2 = 13, как хотелось бы.

person bpachev    schedule 06.08.2016