Spoj-Prime Generator

Question

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?

Answer 1

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()

See this answer for more reasons why this paradigm is followed.

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: