#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";
}