Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ C
Please help me out

I am trying to do the following:
 
"Create a program that calculates prime numbers from a certain number X to a number Y. Modify the program so as to run two threads at the same time. The first thread will start counting from X to Y and the second from Y to Z."
 
I have managed to create the program and get the threads running. My only problem is that for input values greater than 90000, the program is no longer reliable e.g. for a range of 100000 - 150000, the program might output only 1 prime number and if run again output 5 prime numbers and yet another time output 3 prime numbers.
I have tested the program without threads and it works fine, which leads me to think that it's my implementation of the thread that is faulty.
 
Please help me out if you can. Thanks
 
here is my code so far:
 
#include <iostream>
#include <stdio.h>
#include <windows.h>
 
using namespace std;
const int MAX = 10000;
 
struct prArray
{
    int pStart, pEnd, pTest, pCount;
    int tArray[MAX];
};
 
int check_prime(int);
DWORD WINAPI primer(LPVOID lpParam);
 
int main()
{
    /* by having these 2 variables + the struct, error checkin is made easier*/
    int one, two, diff, temp, end1, start2;
 
    cout << " START:\n";
    cin >> one;
    cin >> two;
    prArray ash;
    prArray jeff;
    diff = (two - one); // get the difference between the start and end values
    temp = diff / 2;        // use this to divide the work evenly among the threads
    end1 = one + temp;      // end value for first thread
    start2 = end1 + 1;      // begin 1 number after the end of first thread

    // set the struct values
    ash.pStart = one;       // equal to the first number of the range e.g. 1 - 10000 --> 1
    ash.pEnd = one + temp;  // equal to halfway between the range e.g. 5000
    ash.pCount = ash.pStart;
    jeff.pStart = start2;   // equal to next number after halfway e.g. 5001
    jeff.pEnd = two;        // equal to last number of the range e.g. 10000
    jeff.pCount = jeff.pStart;
 

    //create first thread
    DWORD myThreadID1;
    HANDLE myHandle = CreateThread(
        NULL,           // security
        0,              // stack size
        primer,         // function to perform
        &ash,           // function parameter --> pass the struct
        0,              // creation flag
        &myThreadID1);  // thread id

    //create second thread
    DWORD myThreadID2;
    HANDLE myHandle2 = CreateThread(
        0,
        0,
        primer,
        &jeff,
        0,
        &myThreadID2);
 
    // close the threads
    CloseHandle(myHandle);
    CloseHandle(myHandle2);
 

    // print stuff out
    cout << endl << endl;
    cout << "   BACK TO main()\n";
    // begin with first struct (ash)
    cout << "\n   THREAD1: \n";
    cout << "Thread1 starting point: " << ash.pStart << endl;
    cout << "Thread1 ending point: " << ash.pEnd << endl;
    cout << "Test: " << ash.pTest << endl;
    int i1;
    for (i1 = 0; i1 < MAX; i1++) // print array values for first struct (ash)
    {
        if (ash.tArray[i1] == 0)
        {
            break;
        }
        else
        {
            cout << ash.tArray[i1] << " ";
        }
    }
 
    //begin second thread (jeff)
    cout << endl << endl;
    cout << "   THREAD2: " << endl;
    cout << "Thread2 starting point: " << jeff.pStart << endl;
    cout << "Thread2 ending point: " << jeff.pEnd << endl;
    cout << "Test: " << jeff.pTest << endl;
    int js;
    for (js = 0; js < MAX; js++) // print array values for second struct (jeff)
    {
        if (jeff.tArray[js] == 0)
        {
            break;
        }
        else
        {
            cout << jeff.tArray[js] << " ";
        }
    }
    cout << "\n first = " << i1 << endl;
    cout << " second = " << js << endl;
    cout << "Thread 1 counter = " << ash.pCount << endl;
    cout << "Thread 2 counter = " << jeff.pCount << endl;
    cout << "\n END PROGRAM" << endl;
    system("pause");
    return 0;
}
// =============    END OF main() ==============

/** ============    CHECK FOR PRIME ============= */
int check_prime(int a)
{
    int c;
    if ( a == 2 || a == 3 || a == 5 || a ==7) //check if the number is 2
    {
        return 1;
    }
    else if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0 || a % 7 == 0) //check if the number is even
    {
        return 0;
    }
    else //for odd numbers, check if they are prime
    {
        for (c = 11; c <= a - 1; c+=2)
        {
            if (a%c == 0)
            return 0;
        }
        if ( c == a)
            return 1;
    }
}
/** ============    END CHECK PRIME============== */
 
/** ============    THREAD  ===================== */
DWORD WINAPI primer(LPVOID lpParam)
{
    prArray& dan = *(prArray*)lpParam; /*working initialization */
    dan.pTest = (dan.pEnd - dan.pStart);
 
    // initialize the array to "0"
    for (int i = 0; i < MAX; i++)
    {
        dan.tArray[i] = 0;
    }
 
    int b = 0;
    for (int lp = dan.pStart; lp <= dan.pEnd; lp++, dan.pCount++)
    {
        int result3 = check_prime(lp);
        if (result3 == 1)
        {
            dan.tArray[b] = lp;
            b++;
        }
    }
}
/** ================END THREAD =================*/
Posted 14-Nov-12 4:04am
Comments
Keith Barrow at 14-Nov-12 10:38am
   
This doesn't answer your question (this is why I haven't added a solution), but you can make significant improvements to the checking algorithm:
1. Instead of iterating over all numbers and rejecting if divisible by 2, only iterate over the odd ones (and add two to it in each loop). This halves the number of numbewrs you check.
2. Keep a list of primes you have found. You should check that the prime is not evenly divisible by numbers in this primes list, rather than looping though all divisors. This is related to the sieve of Eratosthenes if you want to Google it. You semi-implemented the first part of this with (a % 2 == 0 || a % 3 == 0 || a % 5 == 0 || a % 7 == 0)!
3. You only need to check divisors from the prime numbers list up to the square root of the number you are checking, e.g. if you are checking to see if 9 is prime, you only need to perform division checks using the primes up to 3.
 
These will significantly improve the performance of app. Also it will clean up the check_prime method, which has a few things wrong with it.
wildesire at 15-Nov-12 10:21am
   
i have actually implemented it so that it checks only odd numbers by adding "a % 2 == 0" which basically takes out all numbers divisible by two (even). As for the part about keeping a list of the primes, someone had mentioned that to me but i couldn't figure out how to implement. i will check out the suggestion you have made. Thanks

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

You do not wait the end of your threads.
You might use the following lines to wait the end of your 2 threads :
HANDLE handles[2];
 
handles[0]=myHandle;
handles[1]=myHandle2;
WaitForMultipleObjects(2,handles,TRUE,INFINITE);
 
CloseHandle(myHandle);
CloseHandle(myHandle2);
  Permalink  
Comments
wildesire at 15-Nov-12 10:22am
   
what? can i really be that simple? i actually read about wait for multiple threads, but i didn't really put that much thought into it. i'll give it a try. Thanks mate

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 mhegazy94 460
1 Sergey Alexandrovich Kryukov 405
2 Kornfeld Eliyahu Peter 275
3 Gihan Liyanage 163
4 Sibeesh KV 156
0 Sergey Alexandrovich Kryukov 6,775
1 OriginalGriff 6,696
2 CPallini 5,345
3 George Jonsson 3,599
4 Gihan Liyanage 2,751


Advertise | Privacy | Mobile
Web01 | 2.8.140922.1 | Last Updated 14 Nov 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100