#include <time.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

const int maxnum=100000;
vector<int> primes1;
vector<int> primes2;
vector<int> primes3;

void Primev1();
void Primev2();
void Primev3();

int main()
{
    cout<<"Calculating Primes...PSketchy's code with uberdev's  correction"<<endl;
    Primev1();
    cout << "Press enter to continue."<<endl;
    cin.get();
    cout<<"Calculating Primes...Yojay's optimizations + only checking for divisility to sqrt(i)"<<endl;
    Primev2();
    cout << "Press enter to continue."<<endl;
    cin.get();
    cout<<"Calculating Primes...Only checking based on previous primes / up to sqrt(i)"<<endl;
    Primev3();

    return 0;
}
void Primev1()
{
    clock_t start, end;
    start = clock();

    for (int i = 2; i <= maxnum; i++)
    {
        bool isPrime = true;
        for (int n = 2; n < i; n++)
        {
            if (i%n == 0)
            {
                // i is divisible by n with no remainder, so it's not a prime
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes1.push_back(i);
            //cout<< "prime:  " << i << endl;
        }
    }

    end = clock();
    cout << "Primes found:"<< primes1.size()<<endl;
    cout << "Time required for execution: "
    << (double)(end-start)/CLOCKS_PER_SEC
    << " seconds." << "\n\n";
}
void Primev2()
{
    clock_t start, end;
    start = clock();
    primes2.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
    //cout<< "prime:  " << 2 << endl;

    for (int i = 3; i <= maxnum; i+=2)
    {
        bool isPrime = true;

        for (int n = 2; n <= sqrt(i); n++)
        {
            if (i%n == 0)
            {
                // i is divisible by n with no remainder, so it's not a prime
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes2.push_back(i);
            //cout<< "prime:  " << i << endl;
        }
    }


    end = clock();
    cout << "Primes found:"<< primes2.size()<<endl;
    cout << "Time required for execution: "
    << (double)(end-start)/CLOCKS_PER_SEC
    << " seconds." << "\n\n";
}
void Primev3()
{
    clock_t start, end;
    start = clock();
    primes3.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
    //cout<< "prime:  " << 2 << endl;

    for (int i = 3; i <= maxnum; i+=2)
    {
        bool isPrime = true;
        for (int j=0; j<primes3.size(); j++)
        {
            if(primes3[j]>sqrt(i))
                break;
            if(i%primes3[j]==0)
            {
                // i is divisible by n with no remainder, so it's not a prime
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes3.push_back(i);
            //cout<< "prime:  " << i << endl;
        }
    }


    end = clock();
    cout << "Primes found:"<< primes3.size()<<endl;
    cout << "Time required for execution: "
    << (double)(end-start)/CLOCKS_PER_SEC
    << " seconds." << "\n\n";
}