C Sieve of Eratosthenes using Fork

Question

I am trying to implement a code in C which has as input a text file, each line in the text file contains a number in increasing order from 2 to N and I want to identify the prime numbers using the Sieve of Eratosthenes. I want to use Fork() for this.

I have found a way to do this with pipes, but I would like to know if there is a way to implement this using fork without pipes.

Here is my code (I am not the best so it is a bit messy)

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>


//Delete multiples
void delete(int p, int r, int w){
    int i;
    while(read(r, &i, sizeof(i))){
        if(i % p != 0){
            write(w, &i, sizeof(i));
        }
    }
}

void primes(int r){
    int p;
    pid_t pid;
    
    if(read(r, &p, sizeof(p))){   
        int primePipe[2];
        pipe(primePipe);
        printf("%d\n", p); //Printing out the numbers
        
        pid = fork();
        if(pid < 0){ // Error with fork
            fprintf(stderr, "Fork Failed");
            exit(1);
        }else if(pid){   //Child
            close(primePipe[1]);
            primes(primePipe[0]);
        }else{   //Parent
            close(primePipe[0]);
            delete(p, r, primePipe[1]);
            close(primePipe[1]);
        }
    }
}
int main(int argc, char *argv[]) {
    int num;
    int pd[2];
    pid_t pid;
    pipe(pd); 
    char fileName[200];
    
    //Take a file as input
    printf("Enter the name of the file: \n");
    scanf("%s",fileName);
    FILE* file = fopen(fileName, "r");
         
    if (! file ){  
      printf("Error, the file cannot be read.\n"); 
      exit(-1); 
    } 
    
    pid = fork();
    if (pid < 0) { //Error with fork
      fprintf(stderr, "Fork Failed");
      exit(1);
      return 1;
    }else if(pid){ //Child
        close(pd[1]);
        primes(pd[0]);   
    }else{ //Parent 
        close(pd[0]);
        while (fscanf(file, "%d", & num) == 1 ){ //Going through the file
               write(pd[1], &num, sizeof(num)); 
        } 
        close(pd[1]);
    }

    exit(0);
}

Answer 1

There are many ways to do interprocess communication but I think pipes are probably the simplest for your purpose which, I assume, is just a learning exercise (forking a new process for each prime number you find is always going to be far more significant than the overhead of reading and writing a pipe).

---

Addendum. This isn't really a sieve of Eratosthenes. You shouldn't need any arithmetic operations other than addition and comparison (any implementation of the Sieve of Eratosthenes that uses the % operator is wrong).

Edit

The original sieve algorithm works like this:

1. Take the first number in the list, call it n. Have another number c which is initially set to n. Record n as a prime
2. Delete c from the list.
3. Add n to c
4. If c is less than the largest number in the list go back to step 2
5. If you haven't run off the end of the list, go to step 1.

You'll need to modify the algorithm slightly for your program. Something like this is needed (not tested or even compiled).

void delete(int p, int r, int w)
{
    int i;
    int c = p + p;
    while(read(r, &i, sizeof(i)))
    {
        if(i < c)
        {
            write(w, &i, sizeof(i));
        }
        else 
        {
            c = c + p;
        }
    }
}