Prime number with threading

Question

I write a code in order to print all the number from a begin to end that the user writes. I want to do this with threading. For example the begin is 1 and the end is 100. I ask the users to enter a N number that is the number of threading that the program create. For example if he enters 10, the program will create 10 thread. The first thread will print primes number from 1 to 10. The second thread will print primes number from 10 to 20. The third from 20 to 30 and son on..

But I have a problem. In fact, my program prints many number in the file that are not primes number, and more than that often I have in the code the same number many times.

This is my code :

void writePrimesToFile(int begin, int end, ofstream&  file)
{
    for (int i = begin; i <= end; i++)
    {
        for (int j = begin; j < end / 2; j++)
        {
            if (i % j != 0)
            {
                file << i << endl;
            }

        }
    }
}

void callWritePrimesMultipleThreads(int begin, int end, string filePath, int N)
{
    ofstream myfile(filePath);
    clock_t startTimer, stopTimer;

    startTimer = clock();

    vector<thread> arr;

    for (int i = 0; i < N; i++)
    {
        int start = begin;
        int finish = N;
        arr.emplace_back(writePrimesToFile, start, finish, ref(myfile));
        start = finish;
        finish += N;
    }
    for (auto& thread : arr)
    {
        thread.join();
    }

    stopTimer = clock();
    cout << "The time that takes is: " << (double)(stopTimer - startTimer) / CLOCKS_PER_SEC << endl;
}

Code in the main:

    callWritePrimesMultipleThreads(1, 100, "primes2.txt", 10);

@AlgirdasPreidžius Anything that can help me to resolve the error. — Rony Cohen, Oct 27 '16 at 14:37
`for (int j = begin; j < end / 2; j++)` is wrong. You should start with `j=2` — Yexo, Oct 27 '16 at 14:39
@RonyCohen Wait, what? That is not the answer to my question. Did you even try using the debugger? What did you observe when using it? Since debugger is the first tool to use, when your code doesn't behave as expected. In a nutshell: your prime detection algorithm is flawed, and the issue doesn't have anything to do with threading. — Algirdas Preidžius, Oct 27 '16 at 14:40
@Yexo Not only that.. `j < end / 2` is wrong as well, in addition to the `if` statement. In a nutshell: every piece of logic is wrong. — Algirdas Preidžius, Oct 27 '16 at 14:41
@AlgirdasPreidžius Whoops, I completely missed the wrong if. I'd think that `j < end/2` should work (although it's far from optimal). — Yexo, Oct 27 '16 at 14:42
First, make sure your prime number generator works in a single thread. Then either protect shared resources (file) with a lock or better avoid shared resources by letting the threads fill in containers of it own and combine and write the results to file in the main thread. — stefaanv, Oct 27 '16 at 14:44
Maybe you should rather write [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) algorithm.. and then use your range dividing per thread during the inner step, when you mark multiplies of next prime found. Your approach looks to be even more naive than the sieve, and it will not bode well with partitioning idea, as each thread, when checking next prime, will have to start at `2` again. — Ped7g, Oct 27 '16 at 15:44

cpatricio · Accepted Answer · 2016-10-27T16:29:18.007

2

Lots of things to fix in your code, primes will start at 1, not 0, also you should start to divide by 2 and not 1 or 0 (you can't divide by 0), after you get rest 0 for one, it is not prime, and it will always end at the number of what you want to calculate (10 % 20 is non sense)

#include <stdio.h>
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <functional>
#include <fstream>
#include <math.h>

using namespace std;
mutex mtx;

void writePrimesToFile(unsigned int begin, unsigned int end, ofstream& f)
{
    for (unsigned int i = begin; i <= end; i++)
    {
        for (unsigned int j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                break;
            }
            else if(j + 1 == i)
            {
                mtx.lock();
                f << i << endl;
                mtx.unlock();
            }
        }
    }
}

void callWritePrimesMultipleThreads(unsigned int begin, unsigned int end, string filePath, unsigned int N)
{
    ofstream myfile(filePath);
    clock_t startTimer, stopTimer;

    startTimer = clock();

    vector<thread> arr;
    unsigned int each = end/N;
    unsigned int start = begin;
    unsigned int finish = start + each - 1;
    for (unsigned int i = 0; i < N; i++)
    {
        arr.emplace_back(writePrimesToFile, start, finish, ref(myfile));
        start += each;
        finish += each;
    }
    for (auto& thread : arr)
    {
        thread.join();
    }

    stopTimer = clock();
    cout << "The time that takes is: " << (double)(stopTimer - startTimer) / CLOCKS_PER_SEC << endl;
}


int main()
{
    callWritePrimesMultipleThreads(1, 110, (string)"primes.txt", 10);
    return 0;
}

Also, added a mutex when writing to file.

edited Oct 27 '16 at 16:29

answered Oct 27 '16 at 16:12

cpatricio

457
1
5
11

Thanks. But I don't understand what is j+1 == i. And why do you write else if instead of simple else ? – Rony Cohen Oct 27 '16 at 16:58
Last element to test will be j+1, if he gets there it's because all other tests pass and is a prime number. – cpatricio Oct 27 '16 at 17:01
Can you give me an example because I don't understand very well – Rony Cohen Oct 27 '16 at 17:05
For i = 5: j=2 5/2 != 0, j=3 5/3 != 0, j=4 5/4 != 0, there is no more tests, so it will write 5 (i) as a prime number. For i = 6: j=2 6/2 == 0, 6 is not a prime number and for ends with break. For i = 7; j=2 7/2 != 0, j=3 7/3 != 0, j=4 7/4 != 0, j=5 7/5 != 0, j=6 7/6 != 0, there is no more tests, 7 is a prime number – cpatricio Oct 27 '16 at 17:09
Thanks a lot. But does it normal that in spite of the mutex the number are not in ascending order, because your code gives primes number but not in ascending order. – Rony Cohen Oct 27 '16 at 17:23
If you are using linux `cat primes.txt |sort -n`, or you can save the primes in a vector and sort and print all at end. – cpatricio Oct 27 '16 at 17:44
@RonyCohen that mutex is there to prevent two numbers to mix together, like one thread outputting 13 and other 101, without mutex you can get "1101 3 " in the file. Why would you even expect the asynchronous thread to produce the result in sorted way? You should seriously think about your way of thinking about parallelism, if you somehow managed to expect that, and figure out how that happened. I mean it must be so obvious, if you imagine how those 10 threads are churning out numbers from their partition in parallel ... ? Having sorted output would require thread 10 to wait for T1-9 finish. – Ped7g Oct 28 '16 at 17:29

score 0 · Answer 2 · answered Oct 27 '16 at 15:06

Look at your loop:

for (int i = begin; i <= end; i++)
{
    for (int j = begin; j < end / 2; j++)
    {
        if (i % j != 0)
        {
            file << i << endl;
        }

    }
}

You're outputting i every time you find a number it's not divisible with.
That's a lot of numbers.
(9 is for instance not divisible with 2, 4, 5, 6, 7, or 8. But it's not a prime number.)

A number is prime if it's not divisible by any number (>=2), not if there's any number it's not divisible with.

It's also not enough to look for factors between begin and end / 2, you need to look between 2 and sqrt(end).

My advice is to write a working single-threaded primality test first, before you start multi-threading and interval-slicing.

Prime number with threading

2 Answers2