<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step1:  Iterators and Generators
In the section on loops we introduced the range function, and said that you should think about it as creating a list of numbers. In Python 2.X this is exactly what it does. In Python 3.X this is not what it does. Instead it creates the numbers one at a time. The difference in speed and memory usage is enormous for very large lists - examples are given here and here.
We can recreate one of the examples from Meuer's slides in detail
Step2:  We will now see how much memory this uses
Step4:  We see that the memory usage is growing very rapidly - as the list gets large it's growing as $N$.
Instead we can use the range function that yields one integer at a time
Step6:  We see that the memory usage is unchanged with $N$, making it practical to run much larger calculations. 
Iterators
The range function is returning an iterator here. This is an object - a general thing - that represents a stream, or a sequence, of data. The iterator knows how to create the first element of the stream, and it knows how to get the next element. It does not, in general, need to know all of the elements at once.
As we've seen above this can save a lot of memory. It can also save time
Step7:  This code needs careful examination. First it defines the list of all prime numbers that it currently knows, primes (which is initially empty). Then it loops through all integers $n$ from $2$ to $N$ (ignoring $1$ as we know it's not prime).
Inside this loop it initially assumes that $n$ is prime. It then checks if any of the known primes exactly divides $n$ (n%p == 0 checks if $n \bmod p = 0$). As soon as it finds such a prime divisor it knows that $n$ is not prime it resets the assumption with this new knowledge, then breaks out of the loop. This statement stops the for p in primes loop early, as we don't need to look at later primes. 
If no known prime ever divides $n$ then at the end of the for p in primes loop we will still have is_n_prime being True. In this case we must have $n$ being prime, so we add it to the list of known primes and return it.
It is precisely this point which makes the code above define a generator. We return the value of the prime number found 
using the yield keyword, not the return keyword, and
we return the value as soon as it is known.
It is the use of the yield keyword that makes this function a generator.
This means that only the latest prime number is stored for return.
To use the iterator within a loop, we code it in the same way as with the range function
Step8:  To see what the generator is actually doing, we can step through it one call at a time using the built in next function
Step9:  So, when the generator gets to the end of its iteration it raises an exception. As seen in previous sections, we could surround the next call with a try block to capture the StopIteration so that we can continue after it finishes. This is effectively what the for loop is doing.
We can now find all primes (less than or equal to 100, for example) that have the form $4 k - 1$ using
<ASSISTANT_TASK:>
Python Code:
def naivesum_list(N):
  
  Naively sum the first N integers
  
  A = 0
  for i in list(range(N + 1)):
      A += i
  return A
Explanation: Iterators and Generators
In the section on loops we introduced the range function, and said that you should think about it as creating a list of numbers. In Python 2.X this is exactly what it does. In Python 3.X this is not what it does. Instead it creates the numbers one at a time. The difference in speed and memory usage is enormous for very large lists - examples are given here and here.
We can recreate one of the examples from Meuer's slides in detail:
End of explanation
%load_ext memory_profiler
%memit naivesum_list(10**4)
%memit naivesum_list(10**5)
%memit naivesum_list(10**6)
%memit naivesum_list(10**7)
%memit naivesum_list(10**8)
Explanation: We will now see how much memory this uses:
End of explanation
def naivesum(N):
  
  Naively sum the first N integers
  
  A = 0
  for i in range(N + 1):
      A += i
  return A
%memit naivesum(10**4)
%memit naivesum(10**5)
%memit naivesum(10**6)
%memit naivesum(10**7)
%memit naivesum(10**8)
Explanation: We see that the memory usage is growing very rapidly - as the list gets large it's growing as $N$.
Instead we can use the range function that yields one integer at a time:
End of explanation
def all_primes(N):
    
    Return all primes less than or equal to N.
    
    Parameters
    ----------
    
    N : int
        Maximum number
        
    Returns
    -------
    
    prime : generator
        Prime numbers
    
    
    primes = []
    for n in range(2, N+1):
        is_n_prime = True
        for p in primes:
            if n%p == 0:
                is_n_prime = False
                break
        if is_n_prime:
            primes.append(n)
            yield n
Explanation: We see that the memory usage is unchanged with $N$, making it practical to run much larger calculations. 
Iterators
The range function is returning an iterator here. This is an object - a general thing - that represents a stream, or a sequence, of data. The iterator knows how to create the first element of the stream, and it knows how to get the next element. It does not, in general, need to know all of the elements at once.
As we've seen above this can save a lot of memory. It can also save time: the code does not need to construct all of the members of the sequence before starting, and it's quite possible you don't need all of them (think about the "Shortest published mathematical paper" exercise).
An iterator such as range is very useful, and there's a lot more useful ways to work with iterators in the itertools module. These functions that return iterators, such as range, are called generators, and it's useful to be able to make your own.
Making your own generators
Let's look at an example: finding all primes less than $N$ that can be written in the form $4 k - 1$, where $k$ is an integer.
We're going to need to calculate all prime numbers less than or equal to $N$. We could write a function that returns all these numbers as a list. However, if $N$ gets large then this will be expensive, both in time and memory. As we only need one number at a time, we can use a generator.
End of explanation
print("All prime numbers less than or equal to 20:")
for p in all_primes(20):
    print(p)
Explanation: This code needs careful examination. First it defines the list of all prime numbers that it currently knows, primes (which is initially empty). Then it loops through all integers $n$ from $2$ to $N$ (ignoring $1$ as we know it's not prime).
Inside this loop it initially assumes that $n$ is prime. It then checks if any of the known primes exactly divides $n$ (n%p == 0 checks if $n \bmod p = 0$). As soon as it finds such a prime divisor it knows that $n$ is not prime it resets the assumption with this new knowledge, then breaks out of the loop. This statement stops the for p in primes loop early, as we don't need to look at later primes. 
If no known prime ever divides $n$ then at the end of the for p in primes loop we will still have is_n_prime being True. In this case we must have $n$ being prime, so we add it to the list of known primes and return it.
It is precisely this point which makes the code above define a generator. We return the value of the prime number found 
using the yield keyword, not the return keyword, and
we return the value as soon as it is known.
It is the use of the yield keyword that makes this function a generator.
This means that only the latest prime number is stored for return.
To use the iterator within a loop, we code it in the same way as with the range function:
End of explanation
a = all_primes(10)
next(a)
next(a)
next(a)
next(a)
next(a)
Explanation: To see what the generator is actually doing, we can step through it one call at a time using the built in next function:
End of explanation
for p in all_primes(100):
    if (1+p)%4 == 0:
        print("The prime {} is 4 * {} - 1.".format(p, int((1+p)/4)))
Explanation: So, when the generator gets to the end of its iteration it raises an exception. As seen in previous sections, we could surround the next call with a try block to capture the StopIteration so that we can continue after it finishes. This is effectively what the for loop is doing.
We can now find all primes (less than or equal to 100, for example) that have the form $4 k - 1$ using
End of explanation
<END_TASK>