prime factorization

general
, ,
1

We are given two integers I and j.we have to print x (I<=x<=j) such that number of divisors of x is maximum.if there are more than 1 x possible then print lowest x and also its number of divisors.

Constraint::

1<=I<=j<=10^9

j-I<=10000
e.g.

Input:

1 10

Output: 6 has 4 factors.

My approach:

  1. segmented sieve upto 10^9.

  2. then brute force from I to j.

Is there any better method??

This is not my homework!!!

One of the regional question from ACM ICPC

Is there any better method??

2

Do you want uniqueness in divisors?

3

Since, you haven’t cleared you want uniqueness in divisors or not, also, there arises the case whether the divisors need to be prime or not. If you want only prime divisors and being unique is not required, then it can be log2(max) since 2 is the smallest prime number. And if you want all unique prime divisors, then the maximum number I suppose will be 2*3*5*7*11... <=max i.e. number formed by product of all prime numbers till the product is less than the maximum allowed value.

If uniqueness is not the thing to work upon, then (nlogn) solution can work for you:

for(i=2;i<=max;i++)
{
  for(j=1;j<=(max/i);j++)
  {
    divisors[i*j]+=1;  // this counts the number of divisors of the number i*j
  }
}
for(i=1;i<=max;i++)
{
  // p= find maximum of all divisors[i]
}
// p is your answer then.

There’s also one more possibility the question may be asked which I can think of, you are given many queries of (i,j) and you have to tell the answer of each one. In such a case, the complexity of the above way will come out to be O(no_of_queries(nlogn)) which may not pass in the given time limit. We can do one more thing here for this case. Compute the answer for every number in the initial given range i.e. from 1 to 10^6. Now, build segment tree of the same with the internal nodes store the maximum number in the range of its childs which has maximum number of divisors. Then each query can be answered in O(logn) time.

Will you please provide the link to the exact question. :slight_smile:

1 Like