Here are some things that may help you improve your code.
Use the required #include
s
The code uses std::vector
which means that it should #include <vector>
. It was not difficult to infer, but it helps reviewers if the code is complete.
Use <cmath>
instead of <math.h>
I infer that you've used <math.h>
instead of <cmath>
because you're invoking sqrt(i)
rather than std::sqrt(i)
. The difference between the two include forms is that the former defines things within the std::
namespace versus into the global namespace. Language lawyers have lots of fun with this, but for daily use I'd recommend using <cmath>
. See this SO question for details.
Use the appropriate constructor
There's not really any reason to push the value of 2 after the stack is created when it could be done all at the same time. In fact, I'd write this:
std::vector<int> primes{2, 3};
Seeding the vector with the first two primes for reasons that will be very clear in the next suggestion.
Use a more efficient algorithm
Of all even numbers, only 2, which is already in the vector, is prime, so thereafter all even numbers may be safely skipped. Further, there's little reason to attempt to divide by 2 if you've skipped all other even numbers. For that reason, I'd write it like this:
for(int i = 3; i < primeCap; i+=2) {
bool isPrime = true;
int lim = std::sqrt(i);
for(int j = 1; primes[j] <= lim; j++){
if(i % primes[j] == 0){
isPrime = false;
break;
}
}
if(isPrime)
primes.push_back(i);
}
Doing this reduces the time by about half.
Use const
where practical
Since primeCap
doesn't seem to change within this program, it would make sense to me to declare it as const
or even constexpr
:
constexpr long int primeCap = 1e8;
Maximize the available numerical range
Assuming we're not hunting for negative prime numbers, wouldn't unsigned numbers make more sense? It's also logical to try to assure that primeCap
and the values in the std::vector
are of the same type -- either unsigned
or unsigned long
.
Avoid memory reallocations
It would save some reallocations and moves if the code were to preallocate the required size. One quick and relatively accurate approximation for the number of prime numbers less than a particular number \$n\$ is \$\frac{n}{\log{n}-1}\$. We can use that to reserve
approximately the right amount of memory:
primes.reserve(primeCap / (std::log(primeCap) - 1));
Avoid break
ing out of loops
It's generally better to put loop exit conditions at the top rather than forcing the reader to hunt for a break
buried somewhere inside the loop. It also often simplifies the code. The for
loop could be rewritten as:
for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
isPrime = i % operator[](j);
}
Consider a custom class
If we need a std::vector
of prime numbers, there's little use in it until it's actually created and populated. For that reason, one way to make sure that it's useful immediately after construction is to create a class with a constructor:
Result
Here's the code with all of these suggestions. It runs about twice as fast as the original for any given range.
#include <vector>
#include <cmath>
#include <iostream>
class Primes : public std::vector<unsigned>
{
public:
Primes(unsigned primeCap)
: std::vector<unsigned>{2,3}
{
reserve(primeCap / (std::log(primeCap) - 1));
for(unsigned i = back()+2; i < primeCap; i+=2) {
bool isPrime = true;
unsigned lim = std::sqrt(i);
for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
isPrime = i % operator[](j);
}
if(isPrime)
push_back(i);
}
}
};
int main() {
Primes primes(1e8);
std::cout << "prime[" << primes.size() << "] = " << primes.back() << "\n";
}
long int
. \$\endgroup\$