Problem 62 Prime Ranges
Back to General discussions forum
I have used sieve of erathasthenes to have a list of prime no upto 3000000 and then using a for loop between the given x and y to find out wheter they are in the list and then running the counter forward +1 but I am getting ans on small range of inputs but on large range of inputs its not giving me an answer.
import math def prime(n): l=[] primes=(n+1) * [True] primes[0] =False primes[1]=False for i in range(2,int(math.sqrt(n))): if primes[i] == True: for j in range(i*i,n+1,i): primes[j] = False for i in range(n): if primes[i] == True: l.append(i) return(l) pr=prime(3000000) a=int(input()) ans=[] for i in range(a): x,y=map(int,input().split()) c=0 for j in range(x,y+1): if j in pr: c+=1 ans.append(c) [print(g,end=' ') for g in ans]
Here is my code. Please see to it and tell me the issue.
Oh my god, why you waste your time getting that useless list of primes :).
Cut your prime() function by half and you will be done with this task.
P. S. Sorry, no more spoilers.
qwerty_one I am not able to understand how cutting my function would be of any help. Here I have a list and I compare them to it.Half list will have half primes. Can you please elaborate more. I am new to programming and trying to improve my concepts.
You don't need even a half of the list of primes (the l variable). Cut your function by half by removing all code which makes list of primes. And just return variable primes from function. Good luck.
On my opinion your code is very slow and ineffective, but doing right thing. I downloaded it and run with the same input as was given me and your program output the same answer as my program do. If you experience problem with some other input, please publish the input here, I will try to check using it.
Alexandr Milovantsev can you tip me how to make fast and effective codes. And thank you all for your advice.
There are several approaches:
- Store calculated primes in set(), not in list(). Than condition
if j in pr:would calculate much faster. I used this simple optimization to your code, because in original form it took too much time to calculate. - Don't use
prarray at all. Instead of it return and useprimesarray directly. Conditionif j in pr:transforms toif primes[j]:. Because it is direct indexing instead of searching, it will be much faster. I think qwerty_one has been meaning this approach. - Don't iterate over numbers while counting primes. Instead for every prime calculate and remember index of this prime. Than for each input x,y pair you can just look up indices and output difference of this indices. I used this approach.
Thanks sir it really helped. Can you also tell me where to read for optimal solutions in python and practice OOP.
Just google for Data Structures and Algorithms . Also check for https://en.wikipedia.org/wiki/TheArtofComputerProgramming