The problem statement
This task is all based on precomputations. Do you remember how we were getting all the prime numbers in na given range with the sieve of Eratoshpen? We will do something like that here. Let us have an array of size 10^7 where the element A[I] shows the smallest prime factor for I. Here is what I am saying, for the number 2 the smallest prime factor is 2, and of course for all the numbers divisible by 2 the answer is the same right?. So, when in sieve of Eratosphen we were just marking the numbers as primes, in here we will give all the numbers which are factors of another prime numbers the value of that prime number if that place hasn't been marked yet. Because there is a case, for 2 in A[14] we write the number 2. Then, when we consider the number 7 the asnwer for A[14] shouldn't be changed to 7. Check teh source code for a better understanding.
This task is all based on precomputations. Do you remember how we were getting all the prime numbers in na given range with the sieve of Eratoshpen? We will do something like that here. Let us have an array of size 10^7 where the element A[I] shows the smallest prime factor for I. Here is what I am saying, for the number 2 the smallest prime factor is 2, and of course for all the numbers divisible by 2 the answer is the same right?. So, when in sieve of Eratosphen we were just marking the numbers as primes, in here we will give all the numbers which are factors of another prime numbers the value of that prime number if that place hasn't been marked yet. Because there is a case, for 2 in A[14] we write the number 2. Then, when we consider the number 7 the asnwer for A[14] shouldn't be changed to 7. Check teh source code for a better understanding.
link has broken ...!!
ReplyDeletelink has broken ...!!
ReplyDeleteI am getting TLE again and again.. please help to me to get out of it
ReplyDelete