Thread: How to use bit array

I wrote some code for class to find prime numbers.The teacher says that I need to revise my code with the requirement below:

1. use a bit array to store the prime number checking. The bit array will also be in the heap.
2. Use the max value of an unsigned 32-bt integer (UINT_MAX) to be the maximum size of the prime number you want to check.

I'm new to C so I have a hard time figuring out how to fix it. Could someone give some hints to help me get started? Thank you for your help.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <getopt.h>
#include <ctype.h>
#include <stdint.h>
 
//function to set all non-primes to 0
void *zero_multiples(void *threadid);
 
//global variables
int m = 0;                  //nums[] array size
int c = 0;                  //number of threads
long int *nums = NULL;      //array of numbers
int *done_sw = NULL;        /* indicates that all threads are complete */
int *did_work_sw = NULL;    /* indicates which threads actually did work */
 
int main (int argc, char *argv[])
{
    pthread_t *threads = NULL;              /* threads structure */
    int rc;                                 /* return code for pthread_create() */
 
    int command = 0;                        /* command line arguments */
    int i = 0, k = 0;                       /* for loops */
 
 
    int debug_level = 0;                    /* used for verbose messaging to screen */
    int done_sw_main = 0;                   /* used to check if all the threads have finished */
    int did_work_howmany = 0;               /* tallies how many threads actually did work */
 
    int n_primes = 0;                       /* tallies the number of primes found */
 
 
    while((command = getopt(argc, argv,  "m:c:v" )) != EOF )
    {
        switch(command)
        {
            case 'm': m = strtol(optarg, (char **) NULL, 10 );
                break;
 
            case 'c': c = strtol(optarg, (char **) NULL, 10 );
                break;
 
            case 'v': debug_level++;
                break;
        }
    }
 
    //print n and c
    if(debug_level)
        printf("m=%d, c=%d\n", m, c);
 
    //allocate nums[] 
    nums = (long int *)malloc(m * sizeof(long int));
    if(nums == NULL)
    {
        fprintf(stderr, "nums out of memory!\n");
        exit( EXIT_FAILURE );
    }
 
    //population nums[] array from 1 to n
    for(i=1; i<m; i++)
    {
        nums[i]=i+1;            //start at index 1 because the number '1' can be zeroed out
    }
 
    //allocate the threads[] array
    threads = (pthread_t *)malloc(c * sizeof(pthread_t));
    if (threads == NULL)
    {
        fprintf(stderr, "Threads: memory allocation error\n");
        exit( EXIT_FAILURE );
    }
 
    //allocate done_sw array
    done_sw = (int *)malloc(c * sizeof(int));
    if(done_sw == NULL)
    {
        fprintf(stderr, "done_sw Out of memory!\n");
        exit( EXIT_FAILURE );
    }
 
    //allocate did_work_sw[] array
    did_work_sw = (int *)malloc(c * sizeof(int));
    if(did_work_sw == NULL)
    {
        fprintf(stderr, "did_work_sw Out of memory!\n");
        exit( EXIT_FAILURE );
    }
 
    //create threads and run zero_multiples
    for(i=0; i < c; i++)
    {
        if(debug_level>1)
            printf("Creating thread %d\n", i);
 
        //create thread to run zero_multiples()
        rc = pthread_create(&threads[i], NULL, zero_multiples, (void *)(intptr_t)i);
        if (rc)
        {
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }
 
 
    //main program wait until all threads are complete
    //exit only when all threads have set their done_sw
    while(done_sw_main < c)
    {
        done_sw_main = 0;
        for(i=0; i<c; i++)
        {
            done_sw_main = done_sw_main + done_sw[i];   //count how many threads are done
        }
    }
 
    //count number of threads that did work
    did_work_howmany = 0;
    for(i=0; i<c; i++)
    {
        did_work_howmany = did_work_howmany + did_work_sw[i];
    }
 
    //count the number of primes found
    if(debug_level)
    {
        n_primes = 0;
        for(k=0; k < m; k++)
        {
            if(nums[k] != 0)
            {n_primes++;}   //primes are all the non 0 numbers remaining in nums[]
        }
        printf("n_primes=%d\n", n_primes);
    }
 
    //stop timer
    status=gettimeofday(&tv_2,0);
 
    //calculate elapsed time
    timeval_subtract(&result,&tv_2,&tv_1);
 
    //report results
    printf("%d %d %d %d\n", m, c, did_work_howmany, n_primes);
 
    //all done
    pthread_exit(NULL);
}
 
 
//Function that each thread executes to zero out multiples of primes they find
void *zero_multiples(void *threadid)
{
    int prime = 0;  //current prime
    int i_prime= 0; //current prime index in nums[]
    int i, k;       /* for looping */
 
    /* Each thread reads nums[] up to sqrt(n)
     If a positive number is encountered, it is prime:
     the number is negated, and all multiples are zeroed
     then continues looping looking for positive (prime) numbers */
    for(i = 0; i*i <= m; i++) /* read nums[] until locate a positive number or until sqrt(n) */
    {
        prime = nums[i];
        i_prime = i;
 
        if(prime>0) //if locate a positive number, it must be prime
        {
            did_work_sw[(int)(intptr_t) threadid]=1; /* indicates that this thread did some work */
            nums[i_prime] = -nums[i_prime]; /* set current prime to negative */
            for (k = i_prime + prime; k < m; k = k + prime) /* mark multiples to 0 */
            {
                nums[k] = 0;
            }
        }
    }
 
    done_sw[(int) (intptr_t) threadid]=1;  //indicate that this thread is complete -- no more primes left
 
    pthread_exit(NULL);
}

Originally Posted by Cocojava

use a bit array to store the prime number checking.

This is poorly worded. You'll be using the bit array to indicate which numbers are not prime or (unknown || prime). It's really 3 states, but the unknowns become not prime or prime as your program iterates to test a range of numbers.

Originally Posted by Cocojava

The bit array will also be in the heap.

This just means you'll allocate the bit array using malloc().

Thank you guys for the tip!