Code:
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main(void)
{ cout << "Input the largest positive integer to check: ";
unsigned int maxN;
cin >> maxN;
int n = (int)sqrt(static_cast<float>(maxN));
int k = (int)sqrt(static_cast<float>(n));
vector<int>primes;
if(maxN > 1)
{ primes.push_back(2);
}
for(int i = 3; i <= n ; i = i + 2)
{ primes.push_back(i);
for(int j = 2; j < i && j <= k; j = j + 1)
{ if (i%j == 0)
{ primes.pop_back();
j = i + 1;
}
}
}
if(n%2 == 0)
{ int p = n + 1;
}
else
{ int p = n;
}
for(int i = p; i <= maxN; i = i + 2)
{ primes.push_back(i);
for(int j = 0; j <= primes.size() - 1; j = j + 1)
{ if(i%primes[j] == 0)
{ primes.pop_back();
j = n + 1;
}
}
}
//for(int j = 0; j < primes.size(); j = j + 1)
//{ cout << primes[j] << " ";
//}
cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n";
return 0;
}
Okay, this is what I have now. I took into account the fact that I only need to check odd numbers to see if they are prime. I checked to see if only adding the number to the vector after it has been proven prime would save time, but I don't know exactly how to do that. Here is the top half of the above code with the only way I could figure to only add the number after it is proven prime.
Code:
int main(void)
{ cout << "Input the largest positive integer to check: ";
unsigned int maxN;
cin >> maxN;
int n = (int)sqrt(static_cast<float>(maxN));
int k = (int)sqrt(static_cast<float>(n));
vector<int>primes;
if(maxN > 1)
{ primes.push_back(2);
}
int r;
for(int i = 3; i <= n ; i = i + 2)
{ r = 0;
for(int j = 2; j < i && j <= k; j = j + 1)
{ if (i%j != 0)
{ r = r + 1;
}
if(r == i - 2)
{ primes.push_back(i);
}
}
}
}