1

I've got something like this:

palindromes=[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 101, 111, 121, ..., 99799, 99899, 99999]
# of course im generating it :)

def isPrime(number):
    for i in range(2,int(number/2)+1):
        if number%i == 0:
            return True
    return False

def removeNonPrimes(palindromes):
    for palindrom in palindromes:
        if isPrime(palindrom):
            palindromes.remove(palindrom)
    return palindromes

palindromes = removeNonPrimes(palindromes)

And it doesnt remove all non primes

I can not figure out why

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
matiit
  • 7,969
  • 5
  • 41
  • 65
  • 1
    Your function `isPrime` should be named `isNonPrime` to make it consistent with its return values. This SO question has more on removing items from a list while iterating http://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating-in-python – Narendra Yadala Oct 16 '11 at 19:16
  • If you want to find all the primes that are palindromes, it is probably faster to find the primes first and then to check which ones are palindromes. – hughdbrown Jul 06 '12 at 02:38
  • @hughdbrown how many palindroms are there below `n`? Say `n = 10^m`, then `numPAL(n) = SUM 10^(ceiling(i/2)) {i=1,2..m} = 2*SUM 10^j {j=1,2..m/2}` let's say it's about `2*sqrt(n)`. Since trial division testing of numbers below `k` is `k^1.5` give or take a log factor, overall testing of palindroms for primality will be about `~ 3*n^0.75`. But generating primes below `n` by Sieve of Eratosthenes takes `~ n*log(log(n))` time. Which is worse. – Will Ness Jul 06 '12 at 15:39

4 Answers4

11

In your code:

def removeNonPrimes(palindromes):
    for palindrom in palindromes:
        if isPrime(palindrom):
            palindromes.remove(palindrom)
    return palindromes

You are modifying (with .remove()) the same list you're iterating over (with in). This is not recommended and you may end up removing different items that you intend.

Instead, consider a list comprehension:

def removeNonPrimes(palindromes):
    return [p for p in palindromes if isPrime(p)]
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
  • Thanks :) It works now, but..why? Logically it was fine in my opinion :) – matiit Oct 16 '11 at 19:14
  • My answer explains why using `remove` in a `for` loop doesn't work. Python disagrees with your opinion. – Greg Hewgill Oct 16 '11 at 19:15
  • 2
    In the original, you are modifying a list while looping over it, which means that Python starts looking at the wrong items. In the list comprehension, the original list is left intact, instead a new one is created. – Jasmijn Oct 16 '11 at 19:52
4

Your return values for isPrime are the opposite of what they should be.

Austin Salonen
  • 49,173
  • 15
  • 109
  • 139
  • 1
    But the logic in `removeNonPrimes` is also opposite. So two negatives make one positive :). – Avaris Oct 16 '11 at 19:09
2

You are iterating through an iterable and simultaneously modifying that iterable. So when one loop is completed, the pointer may not necessarily be pointing to the next item in the original set through which you were iterating.

If isPrime(palindrom) returns True and you remove one item, the length of the list is reduced by one.

Consider a situation where palindromes = [7,8,9,10] and palindrom is having value 8. palindrom is actually pointing to palindromes[1]. After the loop is over, palindrome will be pointing to palindromes[2]. Meanwhile since 8 will be removed from palindromes since it is not a prime. Now palindromes = [7,9,10] and palindrom = palindromes[2] = 10. You can see that the value 9 is never touched.

The moral: Never manipulate the iterable on which you are iterating. It is like cutting the branch of the tree on which you are sitting.

(by the way, the function name should have been isNotPrime rather than isPrime to reflect what it was checking. :) )

Abdul Muneer
  • 925
  • 6
  • 14
0

If you want all the primes that are palindromes, this will work better:

def eras(n):
    last = n + 1
    sieve = [0,0] + list(range(2,last))
    sqn = int(round(n ** 0.5))
    it = (i for i in xrange(2, sqn + 1) if sieve[i])
    for i in it:
        sieve[i*i:last:i] = [0] * (n//i - i + 1)
    return filter(None, sieve)

def is_palindrome(n):
    ns = str(n)
    ns_reversed = ''.join(reversed(ns))
    return ns == ns_reversed

if __name__ == '__main__':
    primes = eras(100 * 1000)
    print [p for p in primes if is_palindrome(p)]
hughdbrown
  • 47,733
  • 20
  • 85
  • 108
  • have you tried to time the both variants? Of course the `isPrime` function of the question must be changed to stop at `sqrt(n)`, not `n/2`. Notice the OP says he "generates" the palindromes, not tests all natural numbers for them. That part is missing. – Will Ness Jul 06 '12 at 15:46
  • No I did not time the variants. That was not my point. But since you asked: on a test of size 1 000 000, OP's code takes 3.250 seconds. My code takes 0.138 seconds. No, I did not optimize the OP's code. My point is that the number of primes is much smaller than the number of palindromic numbers, so calculating the primes first and testing for whether they will be palindromes will be the better approach. – hughdbrown Jul 06 '12 at 16:21
  • Hmmm. I have to amend this comment: the number of palindromic numbers is less than the number of primes. My code is faster because the prime calculation (en masse) is better than the OP's prime testing code (piecewise). – hughdbrown Jul 06 '12 at 16:30
  • just swapping the `sqrt(n)` for the `n/2` in OP's code should massively speed it up. It'd make it `~ n^1.5` or so, instead of `~ n^2`. – Will Ness Jul 06 '12 at 17:02
  • I used this for the prime test: `def isPrime(number): return not any(number % i == 0 for i in range(2, int(number ** 0.5) + 1))` Can we agree that is an improvement? On 1 000 000: 0.900 seconds for OP, 0.136 seconds for my code. – hughdbrown Jul 06 '12 at 17:19
  • interesting... will have to investigate further... did you generate the palindromes directly, or tested them from among the naturals? – Will Ness Jul 07 '12 at 09:51