U can use segmented sieve,calculate all primes under 10^6,perform jumps of all prime its complexity will at most (logn X range_size).because there can at most n/2 multiples for 2,n/3 for 3 ,n/5 for 5 and so on for all primes under 10^6.so basic integration of 1/x = ln(x). which acts as upper bound for complexity i.e., it cannot be larger than that.

we know that if x=p1^a1 X p2^a2 X… depending on p1,p2 … are prime numbers and a1,a2,… are their powers, so total divisors are (a1+1)X(a2+1)X(a3+1) and so on until last prime.

use this for calculation of max sum.

u should notice that every number could have atmost logn prime factors.hence this modified segmented sieve will work.

i am not getting what u exactly want to say , if possible try to share the code of what u want to say ??? If possible ,try to submit that question,then send me the accepted solution

My problem is i am not able to find the prime factors of 10^6 ( between L and R ) numbers that

too of order 10^12 effectively not even by segmented sieve .

accepted solution of spoj prime1(prime generator)

now you just have to modify it, large_factor[fm].push_back p and you will get all prime factors.

large_factor is array of vectors that will consist of prime factors of numbers.rest is on you.

this method will work only on large numbers, as on small numbers you can use lp(least prime) array which is also called smallest prime factor,which can be used to factorise in logn any number less than N.

**Observation1**: Numbers greater than >1e6 can have **atmost** 1 **prime factor that is >1e6**

**Observation2**: Let, **x = a^{p1} * b ^{ p2} * c ^ {p3} ** where a,b,c are prime factors of x

Total factor is (p1 + 1) * (p2 + 1) * (p3 + 1) = P_{1} * P_{2} * P_{3}

Now we have to divide it by one of its prime factor such that number of its divisor become minimum and to do that we will decrease the minimum value out of P_{1} ,P_{2} ,P_{3} by 1 (just try any random case)

So we need to find those p1 ,p2 , p3 by using segmented sieve

First calculate all primes <1e6 and then mark their multiples in the range [l,r] and we will get the prime factors of them and to get the power of them just divide the number by these prime factors.

@ souradeep1999

My problem is i am not able to find the prime factors of 10^6 ( between L and R ) numbers that

too of order 10^12 effectively not even by segmented sieve .

If possible please put your words into code

Thanks

Thanks I solved it finally !!!