Prime numbers in c language

Question

I want to find prime numbers with multithreading and using Sieve of E. function.I write some piece of codes. If the program will run, the user enter a max number and thread number. The program should create threads that given thread number. The program find all prime numbers until the max number. Each thread must check one prime number.

My program doesn't find prime numbers. I write checkPrime function and crossout functions for finding prime numbers efficiently. But it doesn't work. So, I can't check my threads work correctly or not. How can I implement checkPrime function?

There are 3 functions. crossout is for Sieve E. method. checkPrime is for checking is a number prime or not. worker is for thread's function. Each thread must check one prime number.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pthread.h>

#define MAX_N 100000000
#define MAX_THREADS 25

// global values
int threadNumber;
int largestNumber;
int isPrime;
int nthreads,  // number of threads (not counting main())
    prime[MAX_N + 1],
    n,  // in the end, prime[i] = 1 if i prime, else 0
    nextbase;  // next sieve multiplier to be used

// lock for the shared variable nextbase
pthread_mutex_t nextbaselock = PTHREAD_MUTEX_INITIALIZER;

void crossout(int a) {
    int i, j, check;
    for (i = 2; i < largestNumber; i++)
        prime[i] = 1;

    for (i = a; i < largestNumber;)
        if (prime[i])
            for (j = i; i * j < largestNumber; j++)
                prime[i * j] = 0;

}

int checkPrime(int a) {
    int i;
    for (i = 2; i <= a; ++i) {
        if (a % i == 0) {
            isPrime = 1;
            return isPrime;
            break;
        } else
            isPrime = 2;
        crossout(a);
        return isPrime;
    }
}

void*  workerThread(void* t) {

    int lim, base;

    long i, j;
    long tid;

    tid = (long)t;
    printf("Thread %ld starting...\n", tid);

    while (1)  {


        pthread_mutex_lock(&nextbaselock);
        base = nextbase;
        nextbase++;
        // unlock the lock
        pthread_mutex_unlock(&nextbaselock);
        if (base <= lim)  {

            if (prime[base])  {
                checkPrime(base);
                // log work done by this thread
            }
        }
        if (checkPrime(base) == 2)
            printf("Thread %ld done. Prime = %d\n", tid, base);
        pthread_exit((void*) t);
    }

    return NULL;
}

//main function with two parameters :argc and argv
int main(int argc, char** argv) {

    threadNumber = argv[3];
    largestNumber = argv[1];


    int i;

    pthread_t thread[threadNumber];
    int rc;
    long t;
    void* status;

    for (t = 0; t < threadNumber; t++) {
        printf("Main: creating thread %ld\n", t);
        rc = pthread_create(&thread[t], NULL, workerThread, (void*)t);
        if (rc) {
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }

    for (t = 0; t < threadNumber; t++) {
        rc = pthread_join(thread[t], (void*)&t);
        if (rc) {
            printf("ERROR; return code from pthread_join() is %d\n", rc);
            exit(-1);
        }
        printf("Main: completed join with thread %ld \n", t);
    }
}

Answer 1

This is modified version of Sieve of Eratosthenes which is the very simple, interesting and fast. Understand its working as I have tried to explain it using comments. Actually try to understand the run-time allocation of array size to avoid defining a large MAX value and try to code simple by analyzing your algorithm and applying good mathematics along with smart coding knowledge.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
    int *arr;
    int count=0,i=3,j,n;
    arr=(int*)malloc(count+1*sizeof(int)); //set array size to 1
    arr[count++]=2; //stored 2 as array first element
    printf("Find all prime numbers upto :: ");
    scanf("%d",&n); //n is the number up to which prime numbers are required
    here:
    {
        while(i<=n) //start with i=3
        {
            j=0;
            while(arr[j]<=sqrt(i)) //till array element value is less than or equal to root of number under checking
            {
                if(i%arr[j]!=0) //if remainder is not zero check divisibility with next array element
                    j++;              
                else
                {
                    i++;          //if remainder is zero then start checking for another number
                    goto here;
                }
        }
        printf("%d, ",arr[count-1]); //printing the number which was proved as prime last time
        arr=(int *)realloc(arr,(count+1)*sizeof(int)); //increasing array size by 1
        arr[count++]=i; //newly proved prime is stored as next array element
        i++;
    }
    printf("%d, ",arr[count-1]); //print last number proved as prime
}

Answer 2

You are trying to mix two different methods for finding prime numbers. You don't need to use both the iterative division method and the sieve of Eratosthenes. This shows a way of implementing the sieve. Even numbers are ignored in the sieve but treated as special cases in isprime(). But it won't help you find a multi threaded solution, because you can't just hand over different numbers to different threads - each prime builds on the work of the previous prime, starting with the assumption that 3 is prime.

// Sieve of Eratosthenes
#include <stdio.h>
#include <stdlib.h>

#define LIMIT   200

char sieve[LIMIT] = { 1, 1, };                  // 1 for not-prime

int isprime(unsigned n)
{
    if(n <= 2)                                  // special cases
        return sieve[n] == 0;
    if(n % 2 == 0)                              // even numbers are not prime
        return 0;
    if(n >= LIMIT)                              // test range
        exit(1);
    return sieve[n] == 0;
}

int main(void)
{
    unsigned n, p;
    for(n=3; n<LIMIT; n+=2) {                   // odd numbers only
        if (sieve[n] == 0) {                    // if n is prime
            for(p=n*n; p<LIMIT; p+=n*2) {       // ignore even numbers
                sieve[p] = 1;                   // not primne
            }
        }
    }

    printf("Prime numbers are:\n");
    for(n=0; n<LIMIT; n++) {                    // check all numbers
        if (isprime(n)) {                       // if n is prime
            printf("%-4d", n);
        }
    }
    printf("\n");
    return 0;
}

Program output:

Prime numbers are:
2   3   5   7   11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71
73  79  83  89  97  101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199

I'll now show an iterative division method. Once again, even numbers are treated as special cases. I don't often write multi threaded C code, so I can't help you with that. But I hope you can build on this second example to make a multi threaded solution.

// iterative division
#include <stdio.h>
#include <math.h>

#define LIMIT   200

int isprime(unsigned n)
{
    unsigned s, i;
    if(n <= 1)
        return 0;
    if(n == 2)
        return 1;
    if(n % 2 == 0)                              // no even numbers
        return 0;
    s = (unsigned)sqrt(n);                      // limit the loop
    for(i=3; i<=s; i+=2)                        // odd numbers only
        if (n % i == 0)
            return 0;
    return 1;
    }

int main(void)
{
    unsigned n;
    printf("Prime numbers are:\n");
    for(n=0; n<LIMIT; n++) {                    // check all numbers
        if (isprime(n)) {                       // if n is prime
            printf("%-4d", n);
        }
    }
    printf("\n");
    return 0;
}

Program output:

Prime numbers are:
2   3   5   7   11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71
73  79  83  89  97  101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199

There are some pitfalls in both of the above examples when working with larger numbers, but I'll leave them for you to discover.