7
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ 1 is not a prime. \$\endgroup\$ Feb 13, 2014 at 21:43
  • \$\begingroup\$ 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 :) \$\endgroup\$ Feb 13, 2014 at 22:28
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 13, 2014 at 22:33
  • \$\begingroup\$ True that! Being lazy almost never pays back. Thank you! \$\endgroup\$ Feb 13, 2014 at 22:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – DSM
    Feb 14, 2014 at 4:15

1 Answer 1

5
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$ Feb 13, 2014 at 22:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – Sisnett
    Feb 13, 2014 at 23:14
  • \$\begingroup\$ 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! \$\endgroup\$ Feb 13, 2014 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.