Search

27 January, 2016

Generation of Prime Number in c++ according to sieve algorithm


/*
Name: Manoz Kumar Biswas
E-mail: manozcsejust@gmail.com
Start Date: 08-03-2015
Date Update:
Purpose: TO generate a long list of prime number by dynamic programming approach
Input: a list of integer numbers
Output: a list of prime numbers among the integers

*/

#include <iostream>
#include <cmath>

using namespace std;

#define SIZE 121

long int primeList[SIZE];

int main()
{
    //cout << sizeof primeList;
    for(long int i = 2; i < SIZE; i++)
    {
        primeList[i] = 1; //at first we assume all is prime and all the position is marked by 1
    }

    for(long int i = 2; i <= sqrt(SIZE); i++)
    {
        if(primeList[i] == 1)
        {
            for(long int j = i + i; j < SIZE; j = j + i)
            {
                if(primeList[j] != 0){
                      primeList[j] = 0; //all the multiples of i are set to 0 to indicate not prime
                }
            }
        }
    }

    cout << "The list of prime numbers till 121 is" << endl;

    for(long int i = 2; i <= SIZE; i++)
    {

        if(primeList[i] == 1)
        {
            cout << i << " "; //shows only the position that are prime indicated by 1
        }
    }
    return 0;
}