You are going to create a List. You will then fill it with numbers consecutively

ID: 665085 • Letter: Y

Question

You are going to create a List. You will then fill it with numbers consecutively numbered from 2 to n where n is entered by the user.

Create a second List - this one should be a Queue - it is empty.

Once you have the first List filled we are going to use a technique called Sieve of Eratosthenes which uses first queue to fill the second queue. You will need to look at the algorithm for this https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here is the simple method to do this - L1 is the first list, Q1 is the Queue.

1. Go to 1st element in L1 (which will be 2).

2. Because it exists - Push this into Q1 and remove it from L1

3. Iterate through each element of L1 and if the value is divisible by 2 remove it.

4. When done go back to the beginning of the list (the value will be 3 the second time around)

5. Print Iteration 1, Value of L1 (all elements) and Q1 (all elements)

6. Repeat steps 2-5 with this new element - repeat until L1 is empty.

Sample output with input 10

Iteration 0: L1 = 2 3 4 5 6 7 8 9 10, Q1 = ,

Iteration 1: L1 = 3 5 7 9, Q1 = 2

Iteration 2: L1 = 5 7, Q1 = 2 3

Iteration 3: L1 = 7, Q1 = 2 3 5

Iteration 4: L1 = , Q1 = 2 3 5 7

Explanation / Answer

Sieve of Eratosthenes is used to find prime numbers in the most efficient way in a array.

working c code

#include <stdio.h>
#include <string.h>

void markMultiples(bool arr[], int a, int n)
{
    int i = 2, num;
    while ( (num = i*a) <= n )
    {
        arr[ num-1 ] = 1; // minus 1 because index starts from 0.
        ++i;
    }
}

// A function to print all prime numbers smaller than n
void SieveOfEratosthenes(int n)
{
    // There are no prime numbers smaller than 2
    if (n >= 2)
    {
        // Create an array of size n and initialize all elements as 0
        bool arr[n];
        memset(arr, 0, sizeof(arr));

        /* Following property is maintained in the below for loop
           arr[i] == 0 means i + 1 is prime
           arr[i] == 1 means i + 1 is not prime */
        for (int i=1; i<n; ++i)
        {
            if ( arr[i] == 0 )
            {
                //(i+1) is prime, print it and mark its multiples
                printf("%d ", i+1);
                markMultiples(arr, i+1, n);
            }
        }
    }
}

// Driver Program to test above function
int main()
{
    int n = 10;
    printf("Following are the prime numbers below %d ", n);
    SieveOfEratosthenes(n);
    return 0;
}

Navigate

You are going to create a List in Javascript using JSFiddle. You will then fill

You are going to create a Queue. (alternately you can create a list and simply i

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You are going to create a List. You will then fill it with numbers consecutively

Question

Explanation / Answer

Related Questions

Navigate