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 magnitud less than test1() just because 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 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).