I am fairly new to programming and even newer to C++ but I am currently in a class for scientific computing, and our task from two weeks ago was to improve the speed of a primality test program. I regrettably do not have the original code because I wrote over it, but the long and short was that program selects 100,000 integers from 100,000 to 999,999 and checks all numbers from 2 to less than the number.
Needless to say, it took over 17 seconds to run. My code was able to get it down to ~74 milliseconds. I handed in my code last week but it's been bugging me that I don't know if I got it as fast as it could go.
(The area I made is at the bottom, at int CountPrimes
)
#include "stdafx.h"
using namespace std;
using namespace chrono;
int CountPrimes(unique_ptr<vector<int>> const &samples);
seed_seq seed{ 2016 };
default_random_engine generator{ seed };
uniform_int_distribution<int> distribution(100000, 999999);
int main()
{
const auto samples{ make_unique<vector<int>>(100000) };
for (auto &sample : *samples)
sample = distribution(generator);
cout.imbue(std::locale(""));
cout << "Searching vector of "
<< samples->size() << " integers..."
<< endl;
auto startTime = system_clock::now();
int numPrimes = CountPrimes(samples);
auto stopTime = system_clock::now();
auto totalTime = duration_cast<milliseconds>(stopTime - startTime);
cout << "Number of Primes: " << numPrimes << endl;
cout << "Total run time (ms): " << totalTime.count() << endl;
system("pause");
return 0;
}
int CountPrimes(unique_ptr<vector<int>> const &samples)
{
int numPrimes{};
for (const auto &sample : *samples) {
bool isPrime = true;
int n{ 2 };
int m{ 3 };
if (sample % n == 0)
{
isPrime = false;
}
while (m < sample && m < 990)
{
if (sample % m == 0)
{
isPrime = false;
break;
}
m += 2;
}
if (isPrime)
numPrimes++;
}
return numPrimes;
}