CODEWITHSUNDEEP
pythonpython-2.7primes
zwlayer
zwlayer

Reputation: 1824

How could I make my prime generator function faster

to gain hands-on experience, I'm trying to solve the problems in spoj . The problem in the link asks to find all prime numbers between given 2 numbers. So how I implement this with python 2.7

# printing all prime numbers between given two inputs
import math
def findPrimes(num1,num2):
    for num in range(num1,num2+1):
        isPrime=True
        for i in range(2,int(math.sqrt(num))+1):
            if num%i==0:
                isPrime=False
                break
        if isPrime:
            print num


def main():
    inputs=[]
    numOfTestCases=int(raw_input())

    while(numOfTestCases>0):
        line=raw_input()
        numbers=line.split()
        inputs.append(numbers)
        numOfTestCases-=1

    for testCase in inputs:
        findPrimes(int(testCase[0]),int(testCase[1]))
        print ""

main()

However, when I send the code, I get time-exceed limit. How could I make my code fast enough?

Upvotes: 1

Views: 116

Answers (2)

Will Ness
Will Ness

Reputation: 71074

No, the numbers aren't huge in spoj/PRIME1. The sieve of Eratosthenes works extremely well there, but even trial division gets you through there, if you test by primes, and test odds only (or better, only 6-coprimes or 30-coprimes).

You need only find primes below the square root of your top limit, in advance. sqrt(10^9) is about 32,000, so there are only about 3,400 primes to maintain. That's nothing.

6-coprimes: numbers coprime with 6, i.e. with 2 and 3, so there's no need to test divide them by 2 nor 3, when testing for primes. You need to find a way to generate them directly, so there won't be any multiples of 2 and 3 among the numbers you need to test, by construction.

Upvotes: 0

Saeid
Saeid

Reputation: 4265

You should use the Sieve of Eratosthenes and it is quite simple. First you initialize all numbers to be prime. Then for each prime you remove its multiples from the prime list. And it's time complexity is near liner O(nloglogn). Something like this:

N = 1000
is_prime = [1]*N
for i in xrange(2,N):
    if is_prime[i]:
        for j in xrange(2*i,N,i):
            is_prime[j] = 0

This implementation should do just fine. But there are some extra optimizations that you can find them in the link above.
Note that 0 and 1 are not prime.

Upvotes: 1

Related Questions