-4

I was asked this problem in an interview a few days ago and wanted to improve on the solution I had given during it. So far this is what I have. Not sure how to go about making it more efficient. I guess for starters:

1) Does adding the i%2 == 0 line save time?

2) What is the time complexity of the % operator in python? Is there a way to check if a number is divisible by some faster way without using %?

3) The d <= math.sqrt(i) makes use of the fact that it is useless to compute divisors past the square root of i, as d will not divide i nicely until d=i. Does this present the optimal number of steps?

4) I start at d=3 because it's a given that i is odd

5) Going off the 4th point, I increment by 2 instead of 1, since it is a given that i is odd.

def is_prime(i):
    if i < 2:
        return False
    if i == 2:
        return True 
    d = 3
    if i%2 == 0: #skip even numbers 
        return False 
    while d <= math.sqrt(i):
        if i%d == 0:
            return False
        d += 2
    return True
Ritvik Taneja
  • 1
  • 1
    Might be better suited to Code Review stackexchange. Similar [question here](https://stackoverflow.com/a/15285588/314291). Yes, the %2 ==0 is generally beneficial. This approach can be extended to higher primes such as 3, 5 etc, and optimized as a 'wheel of 6 / 30 / 120' etc. You can also build a cache of the first N primes as an optimization. – StuartLC Dec 31 '17 at 07:57

1 Answers1

0

1) in theory no, but in practice yes. It does not reduce time complexity in O notation, but can reduce in practice as you do not consider even numbers. Hence, this program could be 2 times faster.

2) as mentioned in comment, it is generally beneficial.

3) Of course. you have just considered sqrt(i) which reduces time complexity from O(i) to O(sqrt(i)).

4) it is not a question. However, it is true.

5) Again, it is not a question. However, it is reasonable, as you have checked i is not even.

OmG
  • 18,337
  • 10
  • 57
  • 90