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