A prime number cannot be factorized into product two numbers less than it. For e
ID: 3592432 • Letter: A
Question
A prime number cannot be factorized into product two numbers less than it. For example 2,3,5,7,11 are prime numbers but 15 is not since 15 = 3x5. A twin number is a pair of numbers (k,k+2) such that both k and k+2 are prime numbers. For example (3,5), (11,13) and (17,19) are all twin numbers
A) Assume that you have two processors, find a decomposition method that brings a parallel computing algorithm to output the total number of twin numbers in the range [1,n].
B) Extend your solution to m processors for the above problem.
Explanation / Answer
#include<math.h>
#include<stdio.h>
#include<pthread.h>
#define MAX_N 100000000
#define MAX_THREADS 25
// shared variables
int nthreads, // number of threads (not counting main())
n, // range to check for primeness
prime[MAX_N+1], // 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;
// ID structs for the threads
pthread_t id[MAX_THREADS];
// "crosses out" all odd multiples of k
void crossout(int k)
{
int i;
for (i = 3; i*k <= n; i += 2)
{
prime[i*k] = 0;
}
}
void *worker(int tn)
{
int lim,base;
work = 0; // amount of work done by this thread
lim = sqrt(n);
do{
pthread_mutex_lock(&nextbaselock);
base = nextbase;
nextbase += 2;
pthread_mutex_unlock(&nextbaselock);
if (base <= lim) {
// don’t bother crossing out if base known composite
if (prime[base]) {
crossout(base);
work++; // log work done by this thread
}
}
else return work;
} while (1);
}
main(int argc, char **argv)
{ int nprimes, // number of primes found
i,work;
n = atoi(argv[1]);
nthreads = atoi(argv[2]); // mark all even numbers nonprime, and the rest "prime until
// shown otherwise"
for (i = 3; i <= n; i++) {
if (i%2 == 0) prime[i] = 0;
else prime[i] = 1;
}
nextbase = 3;
// get threads started
for (i = 0; i < nthreads; i++)
{
// this call says create a thread, record its ID in the array
// id, and get the thread started executing the function worker(),
// passing the argument i to that function
pthread_create(&id[i],NULL,worker,i);
}
// wait for all done
for (i = 0; i < nthreads; i++) {
// this call says wait until thread number id[i] finishes
// execution, and to assign the return value of that thread to our
// local variable work here
pthread_join(id[i],&work);
printf("%d values of base done ",work);
}
// report results
nprimes = 1;
for (i = 3; i <= n; i++)
if (prime[i])
{
nprimes++;
}
printf("the number of primes found was %d ",nprimes);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.