Thread: Why am I not getting the correct primes?

Hi. I'm a beginner in C and system programming. I need to use multiple process and POSIX shared memory to find all primes between 0 and 100. My code compiles, but the result is not correct, it shows all the multiples of 3 as primes.

My instructor also mentioned that the multi-process portion will fork() the appropriate number of child processes. The parent process will create a POSIX shared memory object to which the sub-processes will attach. I am confused about the things he said about parent process.

Can someone take a look at my code and let me know why I'm not getting the right primes? Your help is greatly appreciated.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <getopt.h>
#include <ctype.h>
#include <stdint.h>
#include <unistd.h>
#include <math.h>
#include <fcntl.h>
#include <signal.h>
#include <errno.h>
 
#define BITS_PER_WORD 8
#define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
#define BIT_OFFSET(b) ((b) % BITS_PER_WORD)
#define SHM_NAME "/cc_prm"
 
 
//function to set all non-primes to 0
void set_notPrime(unsigned int n);
void set_bitmap();
void seed_primes();
int check_Prime(unsigned int n);
unsigned long next_seed(unsigned long cur_seed);
void count_primes();
void prime_process();
void *mount_shmem(char *path, int object_size);
void sieve(unsigned long i);
void nevermore();
 
//global variables 
unsigned long m = 100;                  //maximum number
int c = 5;                            //number of processes
char *prime_nums = NULL;
pid_t *process_array;
int tot_p_num = 0;                    //total number of primes found
 
int main (int argc, char *argv[])
{
//print n and c
    printf("m=%ld, c=%d\n", m, c);
   
   
    struct sigaction action;
   
    sigemptyset(&action.sa_mask);
    //action.sa_handler = nevermore();
    action.sa_flags = 0;
   
   
    sigaction(SIGQUIT, &action, NULL);
    sigaction(SIGINT, &action, NULL);
    sigaction(SIGHUP, &action, NULL);
   
   
    unsigned long primes_size = m / BITS_PER_WORD + 1;
   
    void *addr = mount_shmem(SHM_NAME, primes_size);
    printf("Memory is mounted\n");
   
    prime_nums = (unsigned char *) addr;
       
    set_bitmap();
    printf("Bitmap is set\n");
   
    seed_primes();
    printf("Primes are seeded\n");
   
    prime_process();
    printf("children have lived and died\n");
   
    count_primes();
   
    shm_unlink(SHM_NAME);
   
    int pid = 0;
    while((pid=wait(NULL))!= -1)
    {
       continue;
    }
   
    if(errno!=ECHILD)
    {
       perror("couldn't kill child processes\n");
    }
   
    free(process_array);
    printf("everything has been freed\n");
   
   
    return 0;
}
 
 
void set_bitmap()
{
    prime_nums[0] = 0x00;
    unsigned long i;
    for (i = 1; i < (m/BITS_PER_WORD); i++)
    {
        prime_nums[i] = 0x01;
    }
}
 
 
void seed_primes()
{
    unsigned long i;
    unsigned long j=3;
    unsigned long sqrt_n = sqrt(sqrt(m));
    while (j <= sqrt_n + 1)
    {
        for (i = j; i*j <= sqrt(m)+1; i++)
        {
            set_notPrime;
        }
       
        j++;
        while(!check_Prime(j))
        {
            j++;
        }
    }    
}
 
void set_notPrime(unsigned int n)
{
    prime_nums[WORD_OFFSET(n)] |= (1 << BIT_OFFSET(n));
}
 
 
int check_Prime(unsigned int n)
{
    char bit = prime_nums[WORD_OFFSET(n)] & (1 << BIT_OFFSET(n));
    return bit == 0;
}
 
 
void prime_process()
{
    int i;
   
    for (i = 0; i < c; i++)
    {
       process_array = malloc(sizeof(pid_t) * c);
       pid_t pid;
       switch (pid = fork())
        {
            case -1:
                perror("Forking Error");
                exit(EXIT_FAILURE);
                break;
            //This is the child
            case 0:         
                sieve(i);
                exit(EXIT_SUCCESS);
                break;
            //This is the parent
            default:
                process_array[i] = pid;
                break;
       }
    }
}
 
 
void *mount_shmem(char *path, int object_size)
{
    int shmem_fd;
    void *addr;
   
    //create and resize the file
    shmem_fd = shm_open(path, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
   
    if (shmem_fd == -1)
    {
       perror("Can't open shared memory");
       exit(EXIT_FAILURE);
    }
   
    //resize the file
    if (ftruncate(shmem_fd, object_size) == -1)
    {
       perror("Can't resize shared memory");
       exit(EXIT_FAILURE);
    }
   
    /* map the shared memory object */
    addr = mmap(NULL, object_size, PROT_READ | PROT_WRITE, MAP_SHARED,
         shmem_fd, 0);
   
    if (addr == MAP_FAILED)
    {
       perror("Failure mapping shared memory");
       exit(EXIT_FAILURE);
    }
   
    return addr;
}
 
 
unsigned long next_seed(unsigned long cur_seed)
{
    unsigned long i;
    for (i = cur_seed + 1; i <= sqrt(m); i++)
       if (check_Prime(i) == 1)
           return i;
    return 0;
}
 
void sieve(unsigned long i)
{
    unsigned long min = i * (m / c) + 1;
   
    unsigned long max =(i == c - 1) ? m : min + (m / c) - 1;
    unsigned long j;
    unsigned long k;
    j = 1;
    while ((j = next_seed(j)) != 0)
    {
       for (k = (min / j < 3) ? 3 : (min / j);(j * k) <= max;k++)
        {
           set_notPrime(j * k);
       }
    }
}
 
 
void count_primes()
{
    unsigned long i;
 
    if(m >= 2)
    {
        printf("2\t");
        tot_p_num++;        //2 is prime, add 1 to tot_p_num
    }
   
    for(i=3;i<=m; i = i+2)
    {
       if(check_Prime(i))
        {
            printf("%lu\t",i);
           tot_p_num++;
           
            if (tot_p_num % 8 == 0)
                printf("\n");
       }
    }
    printf("\nThere are %d primes between 0 and %lu\n", tot_p_num, m);        
}
 
 
void nevermore()
{
    ;
}

Thank you for catching that. I used "gcc -std=c99 file.c -o file" to compile on Mac and Linux, I did not get any error or warnings. I removed that already. But I'm still not getting the correct primes.

With GCC, you should be adding the -Wall (all warnings) flag to your compile command. Once I figured out I needed to #define _XOPEN_SOURCE 500, here's what I get:

Code:

$ make prime
gcc -Wall -ggdb3 -std=c99 -o prime prime.c -lm -lpthread -lrt
prime.c: In function ‘main’:
prime.c:65:14: warning: pointer targets in assignment differ in signedness [-Wpointer-sign]
prime.c:81:3: warning: implicit declaration of function ‘wait’ [-Wimplicit-function-declaration]
prime.c: In function ‘seed_primes’:
prime.c:119:7: warning: statement with no effect [-Wunused-value]

Line 65: Whether char is signed or unsigned is implementation/system dependent. Either change the declaration of prime_nums on line 38 or the cast on line 65, to match.
Line 81: You need to #include <sys/wait.h> to use the wait() function. Also, declare pid to be the correct type: pid_t.
Line 119: Already mentioned by Tim. Perhaps you meant to make that a function call?

More detail would help. Post the output you get and tell us what's wrong with it, as well as posting the output you expect to get. Do you get the same wrong output every time? Does your program crash randomly? etc, etc. The more you can tell us about the problem, the easier it will be for us to help you find and fix it.

Thank you so much for the tip. I used your suggestions and fixed the warnings/error, but I'm still not getting the correct primes. Please see below:

Here is what I did and what the output looks like:

gcc -Wall -ggdb3 -std=c99 -o prime prime.c -lm -lpthread

Output:
my_laptop:$ ./prime
m=100, c=5
Memory is mounted
Bitmap is set
Primes are seeded
children have lived and died
2 5 7 9 11 13 17 19
23 29 31 33 37 39 41 43
47 51 53 57 59 61 63 65
67 69 71 73 75 77 79 81
83 85 87 89 91 93 95 97
99
There are 41 primes between 0 and 100
everything has been freed



I believe the correct output is

2 3 5 7 11 13 17 19
23 29 31 37 41 43 47 53
59 61 67 71 73 79 83 89


There are 24 primes between 0 and 100.

Do you mind to give me more hints on how to fix this? I commented out "set_bitmap()" in my main function, but the result is still not correct.

I run it 2 times and got different results.
1.
m=100, c=5
Memory is mounted
Bitmap is set
Primes are seeded
children have lived and died
2 5 7 9 11 13 17 19
23 29 31 33 37 39 41 43
45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75
77 79 81 83 85 87 89 91
93 95 97 99
There are 44 primes between 0 and 100
everything has been freed

2.
m=100, c=5
Memory is mounted
children have lived and died
2 3 5 7 11 13 17 19
23 29 31 37 41 43 47 53
59 61 63 65 67 69 71 73
75 77 79 81 83 85 87 89
91 93 95 97 99
There are 37 primes between 0 and 100

My program finally works. Here is what I did in the main function - 1) I commented out "set_bitmap()" and "seed_primes()" and 2) I moved "

count_primes()" to be after

printf("everything has been freed\n"). I got 25 primes between 1 and 100.

I also figured that I fixed set_bitmap() and I did not have to comment them out to make my program works.

Which sieve is this?