When did the number got included in the list?

[Frankduc]

Hello,

I am puzzle how to understand when integer are integrated to a list. Here's an example i pick up.

import itertools

def prime_numbers():
    #handle the first prime
    yield 2
    prime_cache = [2] # cache of primes

    #loop over positive, odd integers
    for n in itertools.count(3,2):
        is_prime = True

        #check to see if any prime number divides n
        for p in prime_cache:
            if n % p == 0: #p divides n evenly
                is_prime = False
                break

         # is it prime?
        if is_prime:
            prime_cache.append(n)
            yield n

for p in prime_numbers():
    print(p)
    if p > 100:
        break

Starting line 10 odd integers are included in the list prime_cache with intertools.count!
In line 13 the for loop pick up the odd numbers in the prime_cache list to filter which are not divided evenly.

How come the for loop can do that when no append method has been used to include odd numbers in prime_cache list?

Than from line 19, in my mind, its like they added in prime_cache list the primes to the list with already filled of odd numbers?

If at line 13 the for loop would have pick up numbers from n in the first for loop i would of think that it is more logical.

Anyone can explain?

Thank you

[Larz60+]

This code is returning all of the primes less than 102.
If you wanted to not print 101:
change:

for p in prime_numbers():
    print(p)
    if p > 100:
        break

To:

for p in prime_numbers():
    if p > 100:
        break
    print(p)

[Frankduc]

Sorry that was not my question at all.

[Larz60+]

Please show what you expected VS what you get.

[bowlofred]

How come the for loop can do that when no append method has been used to include odd numbers in prime_cache list?

prime_cache is initialized to [2], so it always exists by this point and always has elements inside. (It is grown later on line 20, but that just makes it longer).

Than from line 19, in my mind, its like they added in prime_cache list the primes to the list with already filled of odd numbers?

I don't know what you're asking here. The sequence of odd numbers is checked for primality. If it passes, then it is added to prime_cache.

If at line 13 the for loop would have pick up numbers from n in the first for loop i would of think that it is more logical.

Can you show what you mean in code? Line 13 starts the process of checking an unknown number n against the already known primes to see if it is prime or not.

[deanhystad]

Stop using the word "odd". This code does not work with odd numbers, it works with prime numbers. Not all primes are odd (2) and not all odds are prime.

prime_numbers() is a generator. It returns a prime number, not a list of prime numbers. prime_cache[] is a list of previously found numbers. All non-prime numbers can be represented as a product of prime numbers, so a good way to test if a number X is prime is try to divide it by all prime numbers in the range 2..sqrt(X).

prime_numbers() has two loops. The outer loop (for n in itertools.count(3,2):) runs forever. The inner loop (for p in prime_cache) tests if the number from the outer loop is prime. If the number is prime, the inner loop sets a is_prime = True and ends. The outer loop then checks the value of is_prime. If is_prime is True, the number is added to the prime_cache and yielded. In this case that is the start of the outer loop.

Yield is a strange thing that I've only seen in Python. yield returns a value, but it does not exit the function. When this code (for p in prime_numbers()) askes for the next prime, execution resumes in the prime_numbers() generator immediately after the point of the yield.

Is this version easier to understand?

import itertools
import time

def prime_numbers():
    print("yield 2")
    yield 2
    prime_cache = [2]

    for n in itertools.count(3,2):
        print(f"Test {n}")
        for p in prime_cache:
            if n % p == 0:
                break
        else:
            prime_cache.append(n)
            print(f"Add {n} to prime_cache\nyield {n}")
            yield n

for p in prime_numbers():
    print(p)
    if p > 10:
        break
    time.sleep(1)  # slow things down so you can watch it happen

Output:
yield 2
2
Test 3
Add 3 to prime_cache
yield 3
3
Test 5
Add 5 to prime_cache
yield 5
5
Test 7
Add 7 to prime_cache
yield 7
7
Test 9
Test 11
Add 11 to prime_cache
yield 11
11

There are a lot of primes among odd numbers < 10, but 9 is not one of them. Notice that "Test 9" is not followed by "Add 9 to prime_cache".

Also notice that "yield 2" is only printed once. If prime_numbers() was a function it would start execution at the top each time and "yield 2" would be printed multiple times. As a generator, prime_number() pauses execution between

[Frankduc]

Yield is a strange thing that I've only seen in Python. yield returns a value, but it does not exit the function. When this code (for p in prime_numbers()) askes for the next prime, execution resumes in the prime_numbers() generator immediately after the point of the yield.

I will give you that it is a strange thing, but not unusual. It exist in C# You can see the first example https://docs.microsoft.com/en-us/dotnet/...ords/yield

prime_numbers() is a generator. It returns a prime number, not a list of prime numbers.

True but yield n picks the primes from the list prime_cache? I mean yield 2, inject, if i may say, the number 2, and in prime_cache they also added 2.
They could of returned the list and illiminate yield 2. Anyway whats the point of having a function if you need an if statement to stop the generator.

If i print(prime_cache) at line 11 it will show all primes from 2 to the infinite. I was expecting only [2] and odd numbers at this stage.

Than if i print(prime_cache) at line 17 and after, i would get primes.

My question is why before line 12 i can see the primes?
Its not the first time i see something like that. The number generated by intertools get to the prime_cache list without any use of append! That's what is bugging me.
In C# if you want those numbers to get in the list you must use prime_cache.Add(n); right at line 14 otherwise no numbers are added to the list!

Maybe its the language barrier and i am not explaining myself correctly.

Thank you

[snippsat]

I am puzzle how to understand when integer are integrated to a list.

To add on little for what posted over.
I think you are confused bye how generator works.
Nothing is integrated to a list of prime numbers they are generated on the fly.
The prime_cache.append(n) is just a internal check that is not generating a finish list.

If just run then function you see the name generator.

>>> prime_numbers()
<generator object prime_numbers at 0x0000025E0F88B0B0> 

So when it's a generator then nothing is premade into a list and we can start it at any point.

>>> from itertools import islice
>>> 
>>> for i in (islice(prime_numbers(), 50, 55)):
...     print(i)   
...     
233
239
241
251
257
>>> 
>>> list(islice(prime_numbers(), 1000, 1005))
[7927, 7933, 7937, 7949, 7951]

---

A simpler example.

def even_nums(seq):
    lst = []
    for n in seq:
        if n % 2 == 0:
            lst.append(n)
    return lst

>>> lst = [1, 2, 3, 4, 5, 6]
>>> even_nums(lst)
[2, 4, 6]

With a generator we don't need any list or a return statement.

def even_nums1(seq):
    for n in seq:
        if n % 2 == 0:
            yield n

>>> even_nums(lst)
<generator object even_nums at 0x000001973FD0BD60>
>>> for i in even_nums(lst):
...     print(i)
...     
2
4
6
>>> list(even_nums(lst))
[2, 4, 6]

So it just walks the yield value,this make it memory efficient as not generating any list big or small,
only value bye value is generated into memory.

[deanhystad]

The prime_cache is not a source of prime numbers, it is used to test if a number is prime. This is seen more clearly if I make the cache a function attribute so I can see it from outside the function.

import itertools

def prime_numbers():
    yield 2
    prime_numbers.cache.append(2)

    for n in itertools.count(3,2):
        for p in prime_numbers.cache:
            if n % p == 0:
                break
        else:
            yield n
            prime_numbers.cache.append(n)

prime_numbers.cache = []
for p in prime_numbers():
    print(p, prime_numbers.cache)
    if p > 10:
        break

Output:
2 []
3 [2]
5 [2, 3]
7 [2, 3, 5]
11 [2, 3, 5, 7]

Now you can see that when testing if 3 is prime, the cache only contained 2. When testing for 5 the cache contains 2 and 3. The code does not return a value from the cache, it adds the most recent value to the cache so it can be used to test the next prime number. The cache contains previous primes that are used to test the "prime-ness" of n.

[Frankduc]

Ok i think i get it now.
Wherever you print the prime_cache list inside the inner loop it will be included in the field of influence of the loop. After all you are printing inside the loop and after the list declared.
Make sense.
Sorry for beeing slow.
Thank you all