C Programming Reference >> C Programming Short Notes >>

28/05/07 - 674 Views - Ratings :   4 of 5 / 4 Votes

Simple C Program To Produce A List Of Prime Numbers

Level - Intermediate
      

Here we will be developing a program which produces a list of prime numbers using a simple and efficient algortihm. We develop programs logic in steps below -

Logic 1 - Well one of the easiest and least efficient method can be to pass each number through checkprime function we developed in this article and add it to list if its prime.

Logic 2 - In logic 1 code may work but it uses a function which is designed to find a stand alone prime number without any use of list. This will create a solid time consuming program if list is to be generated for a large cap value. So we use a little modified algo, in which list is used to determine the next prime numbers and so on. The mathematical idea behind is that starting with 2, if a prime number smaller than number being tested divides the being tested number perfectly than the number is prime and if number doesnot have any smaller earlier identifed prime number as factor then we add this number as prime number to list and display it.

Also we declare an Value cap which determine the value till which search for prime number in List will go. You may want to limit this value depending upon your machine and its operating system unless and until you are working on a super computer.

Also we use a static fixed size array for storage and a integer counter to keep count of elements in it but you can use link list as dynamic data source which would be having a lesser limitations.

Also there are more complex algorithms such as Sieve of Eratosthenes and Sieve of Atkin and many more . We will not be using them today but maybe some time else.

Source code below is written in C and is implementation of concept above, It produces a list of prime number as output.

#define CAP 10000
// Change Caps Value To Increase Search Limit.
             

#include <stdio.h>
#include <conio.h>

int counter; //Keep Count of number of items in storage
int liststorage [10000];  //Can store upto 1000 Prime Numbers

void primelist ()
{
 int i,j;
 for (i = 3; i < CAP; i++)   // Loops from 3 to UPPERLIMIT
  {
   for (j = 0; j < counter; j++)
    {
      if (!(i%liststorage[j])) break; // Number is Prime
      if (j == counter-1) //Number is Not Prime
        {
          printf ("\n%d",i);
          liststorage [counter] = i;//Add Item To List
          counter++;//Increment Item Counter
          break;
        }
     }
  }
}
             

int main ()

{
  counter = 1;  // Intialize Counter
  liststorage [0] = 2; // Put 2 in the List
  clrscr ();
  printf ("\nPrime Number List : \n\n2");
  primelist ();
  getch ();
  return 0;
}

Reader Comments -

Add Comments 


Name :    

Reply :   


Rating :  
              5 - Excellent
              4 - Good
              3 - Average
              2 - Poor
              1 - Useless
          
Code :