**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[1000],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[1]=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");

}

#include<omp.h>

main()

{

int prime[1000],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[1]=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:**

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)"?

ReplyDeleteI will illustrate your query with an example:

DeleteSuppose 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.

is it parallel enough ?

ReplyDeleteYes, for sure.

DeleteNice logic..

ReplyDelete