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