Question

Q: Using Python: Am trying to write a code that can be tested. Any assistance will be appreciated.

Would want Help in understanding and solving this example from Data Structure & Algorithms (Computer Science) with the steps of the solution to better understand, thanks.

The purpose of this assignment is the application of queues.

A prime number is a positive integer other than 1 and is divisible only by 1 and itself. For example, 7 is a prime number because the only positive factors of 7 are 1 and 7. On the other hand, 12 is not a prime number because 2, 3, 4, and 6 are also factors of 12.

You are asked to write a function to compute the prime numbers up to a given value. The function is named sieve and it will take an integer n as parameter. The function should return a list that contains all prime numbers up to (and including, if appropriate) n, the numbers in the returned list must be in ascending order.

def sieve (n):

For example:

• sieve (10) ➔ [2, 3, 5, 7]

• sieve (11) ➔ [2, 3, 5, 7, 11]

• sieve (20) ➔ [2, 3, 5, 7, 11, 13, 17, 19]

• sieve (100) ➔ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

The approach we will use is called the Eratosthenes sieve, which is discovered 2,300 years ago by Eratosthenes. We will explain the process in modern language and use a queue data structure in the process.

We start by creating an empty queue and enqueue all the numbers from 2 to n (inclusively, and in ascending order) into the queue.

During each round, the first number k at the front of the queue is a prime number; dequeue and append it to the result. Then we go through each number in the queue and delete the
numbers that are divisible by k. The easiest way to do this is first dequeue a number from the queue, if the number is divisible by k, do nothing (that is, we discard the number), otherwise, enqueue it back to the queue (and keep it). (Note that you may have to keep track the number of dequeues you have to do.)

The process finishes when the queue becomes empty.

Examples:

>>> runTestCase (50) Test 50 failed - expecting a list of length 630, got one of length 1 instead.

from ArrayQueue import ArrayQueue

def sieve (n):     return [1]

Answer 1

Here is the code in python with screenshot

=====================================================================================

def sieve (n):
      
    primes = [True for i in range(n+2)]
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (primes[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * 2, n+2, p):
                primes[i] = False
        p += 1
    # returns the list of primes upto n
    return [i for i in range(2,n+1) if primes[i]==True]


  
print(sieve (10))
print(sieve (11))
print(sieve (20))
print(sieve (100))

=======================================================================================

thanks !