## Tuesday, 9 June 2015

### OPENMP program to find prime numbers from range 1 to n by parallel processing (multi-threading)

Explanation:
In this program, I have used optimized way to find the prime numbers from the range 1 to n.
Logic behind the program is as follows:
I start with the assumption that all numbers from 1 to n are prime numbers. Then I remove 1 from the list as everyone knows 1 is neither prime nor composite number. Then I take next prime number(say i) and remove all its next multiples from the list. Again I take next prime number and remove its next multiples from the list. I continue this process until, for a next prime number i,  i*i is less than 'n' to avoid repetition.
I have used multi-threading to remove multiples of prime numbers from the list (in this case, an array).
For execution, I have used gcc compiler on operating system Linux. gcc and g++ compiler consists of OPENMP library.

Watch OpenMP Basics with Example in following video:

Program (openmpprime.c):
Suppose prime[i]==1 means i is prime number and prime[i]==0 means i is not prime number.

#include<stdio.h>
#include<omp.h>
main()
{
int prime,i,j,n;
printf("\nIn order to find prime numbers from 1 to n, enter the value of n:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
prime[i]=1;
}
prime=0;
for(i=2;i*i<=n;i++)
{

/* multi-threading to remove multiples of prime number i from the list (array) */

#pragma omp parallel for
for(j=i*i;j<=n;j=j+i)
{

if(prime[j]==1)
prime[j]=0;
}

}
printf("\nPrime numbers from 1 to %d are\n",n);

for(i=2;i<=n;i++)
{
if(prime[i] == 1)
{
printf("%d\t ",i);
}
}
printf("\n");
}

Steps for implementation:

To compile:
gcc -fopenmp program-name.c

Note: -fopenmp is used to use OPENMP libraries.

To run:

./a.out

Output:

1. Can you please explain cannot understand the code. what does "i*i is less than 'n' to avoid repetition." mean? and why do we use the loop "for(j=i*i;j<=n;j=j+i)"?

1. I will illustrate your query with an example:

Suppose we have to find out prime numbers from 1 to 20.
Then,

1. Neglect 1 as it is nor prime nor composite. That means we have to find out prime numbers from 2 to 20.

2. We will start with 2 and will remove all multiples of 2 i.e. 2*2, 2*3, 2*4, 2*5......

3. Next, we have to remove all multiples of 3 i.e. 3*2, 3*3, 3*4, 3*5....
Here unnecessarily we are looking for 3*2 as we have already seen 2*3 (in step 2).

4. Next, we will remove all multiples of 4 i.e. 4*2, 4*3, 4*4, 4*5....
Here unnecessarily we are looking for 4*2 and 4*3 as we have already remove 2*4(in step 2) and 3*4(in step 3).

5. I generalize this; suppose you want to remove multiples of i i.e. i*2, i*3, i*4....Here if i=4 then no need to check for i*2 and i*3 as already those cases are considered. Better to start with i*i. That's why the loop for(j=i*i;j<=n;j=j+i).

6. You may also wonder why outer loop for(i=2;i*i<=n;i++).
Now see, we are removing multiples starting from i*i as mentioned in inner loop. If i*i is greater than n, then there is no point to consider i as we have to find prime numbers from 1 to n.

7. Try any example like 1 to 20. you will be understood in more better way.

Thanks a lot for your comment.

2. is it parallel enough ?

1. Yes, for sure.

3. Nice logic..