Strange performance difference

Question

For exercise, I wrote this code:

def BigPrime(numP, plist = [], x = 1, counter =0):
    while len(plist) <= numP:
        if x == 1 or x == 2 or x == 5:
                plist.append(x)
        elif x % 2 is not 0 and int(str(x)[-1]) is not 5:
                for div in plist[1:]:
                        if x % div == 0:
                                break
                else:
                        plist.append(x)
                counter += 1
        x += 1
    return plist, counter

It is a simple algorithm that should return a list of the first n primes. When I tried to optimize it, I wanted to cut down all the possible already know not primes from the range. That brought me to:

int(str(x)[-1]) is not 5

But then when I timed it, I saw that the code ran slower. Why? It worked, and the for iterations were less indeed, but yet it was slower.

Also, when it comes to optimization, I'm a black hole of ignorance. Any further way I could improve it?

Answer 1

Well for starters:

int(str(x)[-1]) is a really expensive operation:

1. Go from integer (x) to a string that represents X
2. Get the last element as a char [-1]
3. Transform that char back to an integer

Given what you're trying to do (find if the last digit is a 5), the same operation can be achieved with x%10==5 or x%51=5 (all integer operations, way less expensive). This could be damaging your performance a lot.

Doing a quick experiment:

$> def test1():
    k = time.clock()
    s = int(str(55)[-1]) is not 4
    t = time.clock()
    print(t-k)

$> def test2():
     k = time.clock()
     s = (55%10 != 4)
     t = time.clock()
     print(t-k)

---

$> test1()
1.682255089008322e-05
$> test2()
1.7107678900174506e-06

test2() takes one order of magnitude less than test1() just because of the type of operations.

For your problem space, I think trying to find useful properties of prime numbers that you can exploit is the best way to optimize. For example, a number N doesn't have a prime divisor greater than Sqrt(N).