Prime Generator Time Limit excedded

#1

whenever i submit my code there is message of TLE but all the custom input seems fine to me can you check my code

#2

Hey @amankharb, the comlexity of your code is quite high, you need to use something like Sieve of Eratosthenes. Read about it and implement the task using it to reduce time complexity.

Hope this solved your doubt.
Plz mark the doubt as resolved in my doubts section. :blush:

#3

i have applied sieve eratosthenes but still my code is not accepted and all the custom inputs are running fine 1d ✓✓ can you also check the way i am accepting input from the user is correct 1d ✓✓ like in c++ where space also act as enter for getting input from the user .It is not so in python?? as i have to use split() function to take my input from the user 1d ✓✓ for m and n

#4

Hey @amankharb, you need to create sieve of eratosthenes, once only, and not for all test cases. Make a sieve of eratosthenes, of 10^8 once before taking any input. And store it somewhere, And now for all test cases, use the same sieve. Also you are taking input the right way.

#5

ok got it but problem is still there and i cant figure it out and one more thing whenever i make list of 108 elements the compiler doesnt show any output but when i make that list to 107 then it shows all the output what is the reason for this

#6

sorry but i wast trying to 10^7 and 10^8 instead of 107 and 108

#7

Hey @amankharb, yes because space requirements are very high, but i guess, you will be able to form sieve of 10^8 but not of 10^9. If you will caluculate space requirements for 10^9, it will come around some 4 gb’s or something like this, and online judge system may not allow you to allocate such huge space.

#8

ok so i have applied the sieve of eratosthenes to 10^7 but still one of the test case fails when i submit the code.can u look at it

#9

Hey @amankharb, you are making sieve again and again for different test cases. As i already said,

Hey @amankharb, you need to create sieve of eratosthenes, once only, and not for all test cases. Make a sieve of eratosthenes, of 10^8 once before taking any input. And store it somewhere, And now for all test cases, use the same sieve. Also you are taking input the right way.

Make two different functions one for making the sieve and other for printing. Call the sieve formation function once only. And call the prime number print function again and again for all test cases.

Hope this resolved your doubt.
Plz mark the doubt as resolved in my doubts section. :blush:

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.