Saturday 5 March 2016

Finding Prime Numbers Between 1 to n in Optimized Way with Implementation in C language

                 In this post, we will see an optimized way to find prime numbers between 1 to n. We will also see its implementation in C Language.           

Explanation:
                 In a conventional way of finding prime numbers from 1 to n, we check whether each number is prime or not by dividing it by numbers less than it. It's complexity becomes O(n2). In this post, I have used optimized way to find the prime numbers between 1 to n whose time complexity is O(n). I have also given C language implementation for this. For execution, I have used gcc compiler on operating system Linux. 

Logic for Optimized way of finding prime numbers:
                 We start with the assumption that all numbers from 1 to n are prime numbers. Then we remove 1 from the list as everyone knows 1 is neither prime nor composite number. Then we take next prime number(say i) and remove all its next multiples from the list. Again we take next prime number and remove its next multiples from the list. we continue this process until, for a next prime number i,  i*i is less than 'n'. 
                 
Time Complexity:
                 Time complexity for this approach will be O(n).

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


#include<stdio.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++)
     {
       /* remove multiples of prime number i from the list (array) */  
      
       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 prime.c

To run:
./a.out

Output:

Explanation about the for loop:

Let us illustrate 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. 





No comments:

Post a Comment