# Spoj-Prime Generator

Question-

Generate all prime numbers between two given numbers.

https://www.spoj.com/problems/PRIME1/

My attempt-

I used segmented sieve method.

t=int(input())
import math
def segsieve(x):
if x==1:
return False
for i in range(2,int(math.sqrt(x))+1):
if x%i==0:
return False
return True

while t>0:
f,l=map(int,input().split())
for j in range(f,l):
a=segsieve(j)
if a==True:
print(j)
t-=1


Issue-

I am getting time limit exceeded. How can I make it faster?

• You never decrement t, so your code runs an infinite loop, exceeding any time limit. Aug 26, 2018 at 6:44
• One important rule on Code Review is not to change or add to the code in your question after you have received answers. See What should I do when someone answers my question?. – In this particular case however it might be tolerated, since the problem of the missing decrement of t (causing an infinite loop) was not addressed in the answer at all. Aug 31, 2018 at 17:32

# Algorithm

## Hint

You don't need to check all integers between 2 and int(math.sqrt(x))+1. You only need to check primes between 2 and int(math.sqrt(x))+1.

# Stylistic

## __main__

I would add a "main function" to your program. This is typically done in Python by:

def main():
...

if __name__ == "__main__":
main()


## sqrt

I technically have not measured the performance of sqrt, but I have more commonly seen your for loop written as:

while i * i < x:
...


unlike the current:

for i in range(2,int(math.sqrt(x))+1):


No need to import math then.

## PEP 8

According to the PEP 8 style guide, you should add a space between the mathematical operations. So for instance, instead of:

if x%i==0:


it should be:

if x % i == 0:

• In your hint it says basically: You don't need to do A, do A instead? Aug 26, 2018 at 6:41
• Umm your hint is saying what I have already done. Aug 26, 2018 at 6:42
• @suyashsingh234 I may have miswrote, but do you check only primes between 2 and sqrt(x)? It looks like you check all integers.
– Dair
Aug 26, 2018 at 7:06
• @Graipher See the comment. I forgot the word "all integers" in the first qualifier.
– Dair
Aug 26, 2018 at 7:06