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
– Padraic Cunningham, Commented May 9, 2015 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
– Nir Alfasi, Commented May 9, 2015 at 21:35
In the future, use 4-space indents because this is literally painful to read. — Shashank
– Shashank, Commented May 9, 2015 at 21:36
for num in isPrime: num is now either True or False, not the index position. — dhke
– dhke, Commented May 9, 2015 at 21:40
@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
– Nir Alfasi, Commented May 9, 2015 at 21:43

dhke · Accepted Answer · 2015-05-09 23:19:18Z

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 9, 2015 at 23:19

answered May 9, 2015 at 21:53

dhke

15.5k2 gold badges42 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

kouty Over a year ago

Fine. It's very kind of you to answer!

kouty Over a year ago

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 Over a year ago

What is "numIsPrime"?

kouty Over a year ago

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.

dhke Over a year ago

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.

|

Collectives™ on Stack Overflow

Modify the iterated list of a for loop inside the loop

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related