Modify the iterated list of a for loop inside the loop

Question

A for loop iterate through a long list. I tried to accelerate the iteration modifying the list (without success). the code:

from math import sqrt
def holeofStrainer():
    isPrime = [False, False] + [True]*999999
    for num in range(3, len(isPrime)):
        if isPrime[num] == False:
            continue
        else:
            for x in range(2, int(sqrt(num)) + 1):
                if num % x == 0:
                    isPrime[num] = False        
                    break
            else:          
                isPrime[num] = True       
                for item in range (2, int(1000001/num) + 2):
                    ple = item * num
                    if ple < len(isPrime):
                        isPrime[ple] = False  
    return(isPrime) 
print(holeofStrainer())

The goal of line 5 is to spare unnecessary calculation.

in lines 14-17 I make the modifications (following the sieve of Eratosthenes, I change the value of the multiples of prime numbers to False) avoiding by this way more calculation through the line 5.

SUMMARY:

Is it possible to modify the loop-iterated list from the loop itself?
If the answer is Yes, why is it not good in my code?

what is `for item in range (2, int(1000001/num) + 2)` doing and what are you actually trying to do with your code? — Padraic Cunningham, May 09 '15 at 21:32
@PadraicCunningham the "sieve of Eratosthenes" is a method to find prime numbers by filtering out all the non-prime numbers in a specific range. — Nir Alfasi, May 09 '15 at 21:35
In the future, use 4-space indents because this is literally painful to read. — Shashank, May 09 '15 at 21:36
@alfasin, I know what a sieve is, I just don't understand what the questions is — Padraic Cunningham, May 09 '15 at 21:36
`for num in isPrime`: `num` is now either `True` or `False`, not the index position. — dhke, May 09 '15 at 21:40
What dhke said, you're looping through True and False stuff and then later treating them as numbers. — Shashank, May 09 '15 at 21:42
@PadraicCunningham the question is a mess, this code doesn't do what it's supposed to do - and the OP instead of trying to make it work is trying to make it more efficient :) — Nir Alfasi, May 09 '15 at 21:43
possible duplicate of [Modifying list while iterating](http://stackoverflow.com/questions/1637807/modifying-list-while-iterating) — Nir Alfasi, May 09 '15 at 21:46
the indentation is now 4 and the num is an index of the list. Sorry, in a panic attack I pasted another version... — kouty, May 09 '15 at 21:51
The code run! It take 1 minute or more. Sorry @alfasin the first sending was erroneous. — kouty, May 09 '15 at 21:58
@kouty, http://stackoverflow.com/questions/23423037/prime-factors-in-python/23423821#23423821 `sieve_of_eratosthenes(10000000) -> 328ms` — Padraic Cunningham, May 09 '15 at 22:00

dhke · Answer 1 · 2015-05-09T23:19:18.387

1

I'm pretty sure, you stumbled into a case of premature optimization, i.e. trying to build fast code without having working code first.

Your outer for loop

for num in isPrime:

iterates over the True and False values in isPrime, not over the numbers or index positions.

            for item in range (2, int(1000001/num) + 2):
                ple = item * num
                if ple < len(isPrime):
                    isPrime[ple] = False

As also noted in the comments by Padraic Cunningham, I have no idea what this part of the code is supposed to achieve. There's also a DRY violation (duplicating the limit number).

If I clean all of this up, I end up with something like

def holeofStrainer(nprimes):
    isPrime = [False, False] + [True] * (nprimes - 1)
    for num in (num for num, numIsPrime in enumerate(isPrime) if numIsPrime):                                            
        for x in xrange(2, int(sqrt(num)) + 1):                                                                           
            if num % x == 0:                 
                isPrime[num] = False
                break                      
     return isPrime

Note the use of xrange() instead of range(). If this is python 2, range() creates a full list when called, which hurts quite a lot for the larger numbers.

holeofStrainer(1000000) takes about 14s to run around here. This probably can be done faster (e.g. by checking and storing only odd numbers in the first place), but there are already working versions on SO that are faster.

edited May 09 '15 at 23:19

answered May 09 '15 at 21:53

dhke

15,008
2
39
56

Fine. It's very kind of you to answer! – kouty May 09 '15 at 22:45
Fine. It's very kind of you to answer! First in the for item... I tried to attribute the value False to each element of the list that correspond to a multiple of a prime number. For me the list is like a dictionnary. the items are boolean response to question is prime?, and the index of the elements are the number we asked is prime about it. – kouty May 09 '15 at 22:52
What is "numIsPrime"? – kouty May 09 '15 at 22:54
Fine. It's very kind of you to answer! First in the for item... I tried to attribute the value False to each element of the list that correspond to a multiple of a prime number. For me the list is like a dictionnary. the items are boolean response to question is prime?, and the index of the elements are the number we asked is prime about it. The iteration create all the multiples of the prime number they are corresponding to index of elements of the list. – kouty May 09 '15 at 23:02
`numIsPrime` is the value `True`/`False` from the `isPrime` list for the number at offset/position `num`. In your code you use `False` to indicate *is provable not prime* and so I stuck with that. The list comprehension is more or less equivalent to guarding the loop's contents by `if not isPrime[num]`. In your original code, you never obtained the actual position/number from the list, only the `True`/`False` value. – dhke May 09 '15 at 23:12
I understand partially. Thanks a lot!... But one point remain to clarify! I want to make use of the intermediate results, and introduce an "else statement" after the "break" and iterate the multiples of each prime number (obtained before the end of the loop) that are small to nprimes. Is it possible despite – kouty May 10 '15 at 04:36
Now it is time for me to learn enumerate function. Know you a good and easy tutorial? – kouty May 11 '15 at 03:29
I think the docs are quite good (and short); enumerate by example: https://docs.python.org/2.3/whatsnew/section-enumerate.html – dhke May 11 '15 at 06:54

Modify the iterated list of a for loop inside the loop

1 Answers1