You are not logged in. Please login at www.codechef.com to post your questions!

×

prime factorization

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??

asked 24 Jan '15, 14:53

johncarter's gravatar image

3★johncarter
824
accept rate: 0%

edited 24 Jan '15, 14:54

Do you want uniqueness in divisors?

(24 Jan '15, 17:55) damn_me3★

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. :)

link

answered 24 Jan '15, 18:01

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

edited 24 Jan '15, 18:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×303
×199
×98

question asked: 24 Jan '15, 14:53

question was seen: 2,632 times

last updated: 26 Jan '15, 14:08