Write a multi - threaded C program to find all prime numbers up to N using Sieve

Question

Write a multi - threaded C program to find all prime numbers up to N using Sieve Eratosthenes Algorithm (where N is an integer greater than 1). to find the prime numbers up to N, your program will use Pthreads library to implement a pipelined parallelism model. Your program will need N as a command line argument. See references [1 -5] and sample outputs for examples. The pipeline model is based directly on the same work that is used in CPUs and on factory floors. Each processing element will do a certain amount of the job, and then pass the partly completed task on the next element. Here the processing elements are threads, and each thread is going to do a portion of the task, then pass the partial result on to the next thread. A pipeline model of parallelism, is where: A given thread T_0 performs some computation and second result to thread t_1 Then, T_1 computes its computation and passes result to T_2 and so on. The Sieve Eratosthenes algorithm is expressed as follow. 1. Create list of unmarked natural number a 2, 3..., n 2. k = 2 its the first in the list 3. repeat (a) Mark all multiple of k between k^2 and n (b) set k to the smallest unmarked numbers > k small k^2 n 4. the unmarked numbers are primes Using a pipelined parallelism approach: Each thread keeps the next prime number And if a new number is not divisible by the prime at T_1 send it to T_i +1 Thread T_0 starts reading numbers, and checks if the number is divisible by 2 If the number is not divisible, its is passed to T_1. T_1 will have the second prime number. T_1 passes only the numbers that are not divisible to T_2 and so on. An example of finding prime numbers up to N = 61 using Sieve algorithm graphically is shown as follow. REQUIRMENT IS: Your code should be well document in terms of comments. For example, good comments in general consist of a header (with your name, course selection, date, and brief description), comments for each variable, and commented blocks of code. Your program should correctly implement the Sieve algorithm, along with proper implementation of the Pthreads library function, and pipeline model. Your program should be named "minor4, c", without the quotes. Your program will be graded based largely on whether its work correctly on the CSE machines, so you should make that your program complies and run on a CSE machine. This is an individual programming assignment that must be the sole work of the individual student.

Explanation / Answer

// Minor4.c : Program in C language to implement Sieve of Eratosthenes Algorithm to find prime numbers.

#include <stdio.h>
#define CAP 3600000 /*size of integers array*/
#define PRI 120000 /*size of primes array*/

int main(){
    int i,j,numbers[CAP];
    int primes[PRI];

    /*filling the array with natural numbers*/
    for (i=0;i<CAP;i++){
        numbers[i]=i+2;
    }

    /*sieve the non-primes numbers*/
    for (i=0;i<CAP;i++){
        if (numbers[i]!=-1){
            for (j=2*numbers[i]-2;j<CAP;j+=numbers[i])
                numbers[j]=-1;
        }
    }

    /*transfer the prime numbers to their own array*/
    j = 0;
    for (i=0;i<CAP&&j<PRI;i++)
        if (numbers[i]!=-1)
            pri[j++] = numbers[i];

    /*display the seived prime numbers*/
    for (i=0;i<PRI;i++)
        printf("%dn",PRI[i]);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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