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[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:







5 comments:

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

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

      Delete