2

我为类写了一些代码来查找素数。

老师说我需要按照以下要求修改我的代码:

  1. 使用位数组存储质数检查。位数组也将在堆中。
  2. 使用无符号 32 位整数 (UINT_MAX) 的最大值作为要检查的素数的最大大小。

我不想要一个完整的答案,因为这是我的作业。

但是,有人可以提供一些提示来帮助我入门吗?

我是 C 的新手,所以我很难弄清楚如何解决它。

#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);
}
4

1 回答 1

1

不确定这是否对您有帮助,但这里是位域,被制成一个数组。这是一个基本的位域:

struct
{
    type [member_name] : width ;
};
于 2013-08-19T13:03:55.267 回答