Prime Numbers

Find all the prime numbers less than or equal to a given integer n

Prime Number Generation upto a specific count:

#include<stdio.h>
 
main()
{
   int n, i = 3, count, c;
 
   printf("Enter the number of prime numbers required\n");
   scanf("%d",&n);
 
   if ( n >= 1 )
   {
      printf("First %d prime numbers are :\n",n);
      printf("2\n");
   }
 
   for ( count = 2 ; count <= n ;  )
   {
      for ( c = 2 ; c <= i - 1 ; c++ )
      {
         if ( i%c == 0 )
            break;
      }
      if ( c == i )
      {
         printf("%d\n",i);
         count++;
      }
      i++;
   }         
 
   return 0;
}

There are many logic to check prime numbers, one given below is more 

efficient then above method.
for ( c = 2 ; c 
//only checking from 2 to square root of number is sufficient. 

Program for Prime Number or not:

#include<stdio.h>
main()
{
   int n, c = 2;
 
   printf("Enter a number to check if it is prime\n");
   scanf("%d",&n);
 
   for ( c = 2 ; c <= n - 1 ; c++ )
   {
      if ( n%c == 0 )
      {
         printf("%d is not prime.\n", n);
  break;
      }
   }
   if ( c == n )
      printf("%d is prime.\n", n);
 
   return 0;
}

Prime Numbers Less than a number:

#include <stdio.h>
#include <iostream>
int main()
{
   int n,i=1,j,c;
   printf("Enter Number Of Terms");
   printf("Prime Numbers Are Following\n");
   scanf("%d",&n);
   while(i<=n)
   {
      c=0;
      for(j=1;j<=i;j++)
      {
              if(i%j==0)
        c++;
       }
           if(c==2)
           printf("%d\n",i);
           i++;
        }
        system("pause");
        return 0;
}

Efficient Method for Prime Numbers:

We can use Sieve of Eratosthenes method:

• Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
• Initially, let p equal 2, the first prime number.
• Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
• Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
• Repeat steps 3 and 4 until p2 is greater than n.
• All the remaining numbers in the list are prime.
  
  void GeneratePrimes(int N)
  { bitset<1000> b;
  for(int i = 2; i < N; i )
       { if(!b[i])
                { //Mark all multiples of i to 1 as there are not prime numbers int k = 2;
                while((i * k) < N){ b[i * k] = 1; k ; }
       }
    for(int i = 2; i < N; i )
           { if(!b[i]) cout << i << " "; }
  }

Links:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes