IsPrime()

Hey! Long time no see. Let’s start.

So I was just googling random stuff regarding Maths(I love it.) about triangle and circles. You might be wondering what am I doing ?

Go on read…

Actually I was in metro coming back home, there was this 10th class chubby boy trying to solve a problem based on property of similar triangles and circles. So what? Any guess… I helped him solve that question , the boy was happy and left by saying I never thought strangers can help I replied well some do :).Feels good

Anyways where were we? Um googling maths, so I came across those project euler problems. They are very popular, I remember people solving them when we were in first year, Though I never tried. So why not now? for fun :P

There was this problem no. 7 For this I had to test whether the passed no. Is a prime or not? Here’s what I wrote first

def isPrime(num):
    if num == 2:
        return True
    for n in range(3, int(num ** 0.5) + 2, 1):
        if num % n == 0:
            return False
    return True

It was very slow for large no.s. But I found out that using range() not a good choice, because it will create a list of numbers, which uses a lot of memory.

Then I used xrange(),here is the code:

def isPrime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in xrange(3, int(num ** 0.5) + 2, 2):
        if num % n == 0:
            return False
    return True

Though it was faster than earlier one but this solution also gave an error termination due to time out. Why? I thought xrange() was the best choice since it creates a generator which doesn’t require any memory, but the problem is it raises an OverflowError for very large no.s like 2^31.

Then I came across 2 functions of itertools : count() and islice()

def isPrime(n):
    if n < 2: return False
    return all(n%i for i in islice(count(3,2), int(sqrt(n)-1)//2))

This was faster but I needed to optimise more, thought of a silly thing ,but the results surprised me

def isPrime(n):
    if n < 2: return False
    for i in islice(count(3,2), int(sqrt(n)-1)//2):
        if n%i ==0:
            return False
    return True

You would not believe me but the if-else check was faster than all() and solution got accepted for all the testcases :D. This code could find large primes in only few seconds.

It was fun doing this. Wrote a post after a long time! Goodbye!