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

1 Answer 1

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\$
4
  • \$\begingroup\$ In your hint it says basically: You don't need to do A, do A instead? \$\endgroup\$
    – Graipher
    Aug 26, 2018 at 6:41
  • \$\begingroup\$ Umm your hint is saying what I have already done. \$\endgroup\$ Aug 26, 2018 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, 2018 at 7:06
  • 1
    \$\begingroup\$ @Graipher See the comment. I forgot the word "all integers" in the first qualifier. \$\endgroup\$
    – Dair
    Aug 26, 2018 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.