3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You never decrement t, so your code runs an infinite loop, exceeding any time limit. \$\endgroup\$ – Graipher Aug 26 '18 at 6:44
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin R Aug 31 '18 at 17:32
2
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.