/*
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;
}