i want to find number of factors of a number say 900 that are less than its square root. eg: there are 27 factors of 900 and i want to find number of factors smaller than root of 900 i.e, 30 which are 1,2,3,4,5,6,9,10,12,15,18,20,25.
i currently have this program that finds the number of factors by calculating the number of prime factors. eg:prime factors of 140 are:2^2*5*7. So the number of factors are:(2+1)(1+1)(1+1) [multiplication of powers of prime factors]
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);
}
}
here i am getting number of factors eg:27 factors for 900 but i want to find number of factors that are less than 30. Thanks for help.
If you have the number of factors of n, simply integer divide by 2 to get the number of factors less than the square root. This works because each factor d of n less than sqrt(n) corresponds to a factor greater than sqrt(n) (namely n/d), so the number of such factors will be half the total (unless n is a perfect square, in which case sqrt(n) is an extra factor). However, integer division by 2 takes care of that corner case. Indeed, 27/2 = 13 as desired.