PrimeNoList

#include <iostream>
#include <vector>
#include <math.h>
#include <cstdlib>

//Prime No. List using SIEVE OF ERATOSTHENES

using namespace std;

int main(int argc, char *argv[]) {
    int n;
    vector<int> vec;
    if(argc==1) {
        cout << "Enter a positive decimal number: ";
        cin >> n;
    } else n=atoi(argv[1]);
    for(int i=0;i<=n;i++) {
        vec.push_back(1);//Initially assume all numbers are prime
    }
    vec[0]=vec[1]=0;//0 and 1 are neither prime nor composite
    for(int j=2;j<=sqrt(n);j++) {
        if(vec[j]==1) {
            for (int k=2;k*j<=n;k++) { //Set all the multiples to 0
                vec[k*j]=0;
            }
        }
    }
    //Trial Division Method
    // for(int j=2;j<=n;j++) {
    //  for(int k=2;k<=sqrt(j);k++) {
    //      if(j%k==0) {
    //          vec[j]=0;
    //          break;
    //      }
    //  }
    // }
    for(vector<int>::size_type i=2;i<=vec.size();i++) { //Only numbers left with value 1 are prime
        if(vec[i]==1)
            cout << i << endl;
    }
    return 0;
}

/*
Test Results:
when n=99990000,
Sieve of Eratosthenes method took 35.183s
Trial Division Method method took 9m16.998s
*/