# Strange performance difference

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?

• 1 is not a prime. Feb 13, 2014 at 21:43
• Yeah you're right, the number 1 has been excluded from the prime numbers. We can say that the number 1 is kind of inconvenient for the mathematical pattern of prime numbers, we can say that you can factor any non prime number into a product of primes, like: 24 = 3 * 2^3. If we include the 1 we can write it like: 24 = 3 * 2^3 * 1^153 and nothing would change. But 1 still remains a prime afterall because he follow the general rules nPrime = 1 x nPrime ( 1 = 1 x 1 ). I just don't care being this formal for this little algorithm :) Feb 13, 2014 at 22:28
• Putting 1 into plist forces you to write the loop as for div in plist[1:]: whereas if you left it out you could write for div in plist: and avoid the copy. Feb 13, 2014 at 22:33
• True that! Being lazy almost never pays back. Thank you! Feb 13, 2014 at 22:36
• Aside: don't use is not 0, use != 0; is tests identity, and you want to test equality. It's only an implementation detail that it works at all.
– DSM
Feb 14, 2014 at 4:15

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).

• Well, that's what i feared. I tried that way because i thought that as it went further and further with the numbers it would become harder simply dividing by 5 than just looking at the last digit. Is that option always faster than the other? At what order of magnitude could change? Feb 13, 2014 at 22:34
• I can't answer all of the details as it would depend a lot on how Python implements some operations internally, but I think I can guarantee you that dividing by 5 will always be cheaper, because going from an integer to a string always requires at least 1 modulus (division) operation, making it at least as expensive as the original division anyway. Feb 13, 2014 at 23:14
• Awesome! Thank you, then it's never going to be cheaper if i have to do two divisions at least for that instruction, plus the iteration for the [-1] part, as you said. You've been of great help! Feb 13, 2014 at 23:26