0

I need to fine the first 10000 prime numbers using six threads and print them in order. How can i improve my solution?

#define N 6
#define S 10000

int a[S] = {0};

int is_prime(int n){
  int k;
  if(n == 2)
    return 1;
  for (int i = 2; i<n; i++){
    k = n%i;
    if(k == 0)
      return 0;
  }
  return 1;
}

void* prime_number(void* arg){
  int num = (int *) arg;
  for(int i = (S/N)*num; i<(S/N)*(num+1) && i<S; i++){
    if(is_prime(i))
      a[i] = i;
  }
  pthread_exit(NULL);
}

int main(int argc, char const *argv[]) {
  pthread_t *th;
  th = malloc(sizeof(pthread_t)*N);
  for(int i = 0; i<N; i++){
    pthread_create(&th[i], NULL, prime_number, i);
  }
  for(int i = 0; i<N; i++){
    pthread_join(th[i], NULL);
  }
  for(int i = 0; i<S; i++){
    if(a[i] != 0)
      printf("%d ", a[i]);
  }

  printf("\n");
  free(th);
  return 0;
}

In my solution I save everything in the a array and then I print it. Is there a better way to calculate if a number is prime and, if so, print it without save it in the array?

I need to print the numbers in order.

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
Bob Rob
  • 164
  • 2
  • 10
  • 3
    How about utilizing all 6 threads for checking a *single* number? Like make your `is_prime` multithreaded. That's just wild idea, by the way. – Eugene Sh. Jul 17 '19 at 20:24
  • Good idea, i can consider it; even if i would prefer to don't modify the is_prime function – Bob Rob Jul 17 '19 at 20:28
  • Welcome to SO! Why don't you want to modify `is_prime`? As written, it's extremely inefficient, so it should be the first place to look. It seems like you'll want to write something like a [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), then figure out how to multithread it. What exactly are your goals with this project? Why do you want to print without saving it in an array (surely, this would destroy efficiency if I'm thinking straight)? [This post](https://stackoverflow.com/a/18885065/6243352) is in C# but has a lot of generic advice which may be useful. – ggorlen Jul 17 '19 at 20:31
  • It's a school homework, the funcion is_prime isn't important for my goals (I can assume that it is efficent), the problem is the efficency of the rest of the program, and in particular the big array a – Bob Rob Jul 17 '19 at 20:36
  • I think the big array `a` is a reasonable way to do what you're trying to do. – Barmar Jul 17 '19 at 20:41
  • You can save memory by making it an array of booleans instead of putting the value `i` in `a[i]`. `a[i]` is either `1` or `0` depending on whether `i` is prime. Then the printing loop prints `i` rather than `a[i]`. – Barmar Jul 17 '19 at 20:42
  • But 10K ints instead of 10K chars is not a big deal these days. – Barmar Jul 17 '19 at 20:43
  • @Barmar The list of primes is pretty sparse, so 10K primes will result in *much* longer array of booleans. And it's size is not known initially. – Eugene Sh. Jul 17 '19 at 20:45
  • 1
    @EugeneSh. If that's what he's supposed to be doing, his code is wrong. He's getting all the primes below 10K, not the first 10K primes, unless I'm misunderstanding it. – Barmar Jul 17 '19 at 20:47
  • 2
    All primes below 10,000 is a significantly different problem from the first 10,000 primes. For the former, a school assignment for elementary threads lessons anticipates you partitioning the range into six segment (such as 1 to 1666, 1667 to 3333, and so on), letting each thread finding the primes in each segment, and printing the results. Each thread can be allowed to report its own results, and only one synchronization per thread is necessary (thread finishes its work, waits for go-ahead, then prints results, and the parent gives the go-aheads in order by assigned segment), or… – Eric Postpischil Jul 17 '19 at 21:02
  • 1
    … the parent could collect the results from the threads and report them in order (each thread could allocate memory to return its results and return a pointer to the parent, or the parent could assign each thread a buffer). – Eric Postpischil Jul 17 '19 at 21:02
  • The 10,000th prime is 104,729, whereas there are 1,229 primes less than 10,000 (the last is 9,973). – Jonathan Leffler Jul 17 '19 at 21:09
  • @ggorlen the Sieve of Eratosthenes is indeed a good way to identify primes, much more efficient than the OP's approach, but it parallelizes very poorly because of its extensive data dependencies. – John Bollinger Jul 17 '19 at 21:47
  • Yeah, intuitively it doesn't feel very parallelizable, but the link I posted shows an impressive 25x speed increase with parallel SOE over a poor implementation. I didn't read it in detail, so there might be other non-MT reasons for the increase. Either way, it probably doesn't matter since it sounds like primes are incidental to the program and OP just is calling function X from N threads and printing some ordered results. – ggorlen Jul 17 '19 at 21:59

1 Answers1

0

Get rid of your threads and just optimize your is_prime function. If you're trying to print out every single prime you've found, the printing is going to be a significant fraction of the work you're doing and that won't parallelize at all, so why bother with the threads?

David Schwartz
  • 179,497
  • 17
  • 214
  • 278