#include <iostream> #include <vector> #include <cmath> #include <cassert> #include <ctime> using namespace std; long gcf(long x, long y) { long max = (x >= y ? x : y); long result = 1; for (long factor = 2; factor <= max; ++factor) { if (x % factor == 0 && y % factor == 0) { result = factor; } } return result; } int main() { int size; cout << "Find primes up to: "; cin >> size; clock_t start, stop, middle; double t = 0.0; assert((start = clock())!=-1); int wheelsize = 210, i, j; vector<int> spokes; for (i = 1; i < wheelsize; i++) { if (gcf(i, wheelsize) == 1) { spokes.push_back(i); } } vector<int> diffs; for (i = 1; i < spokes.size(); i++) { diffs.push_back(spokes[i] - spokes[i-1]); } diffs.push_back((wheelsize-spokes[spokes.size()-1])+1); vector<int> primes; primes.push_back(2); primes.push_back(3); primes.push_back(5); primes.push_back(7); for (i = 1; i <= size; i) { for (j = 0; j < diffs.size(); j++) { i += diffs[j]; if (i > size) { break; } primes.push_back(i); } } for (i = 0; primes[i] < sqrt(size); i++) { // need to speed up this section if (primes[i] != 0) { for (j = i+1; j < primes.size(); j++) { if (primes[j] % primes[i] == 0) { primes[j] = 0; } } } } // to here stop = clock(); t = (double) (stop-start)/CLOCKS_PER_SEC; int found = 0; for (i = 0; i < primes.size(); i++) { if (primes[i] != 0) { // cout << primes[i] << " "; found++; } } cout << "\nRun time: " << t << " seconds.\n"; cout << found << " primes found.\n"; int x; cin >> x; }

However, my original sieve slows the program down drastically. To find 10,000,000 primes, it takes .3 seconds to get an array of 2.3 million possible primes, but takes 94 more seconds to take that down to the 660,000 primes. It seems to me that there has to be a better way to do this, but I have no idea how to go about it and after an hour of Google searching I decided to post it here. I don't need code, just a general idea of how I would make the marked section work better. Feel free to move this where ever it should go.