# Finding primes optimization

Page 1 of 1

## 2 Replies - 1157 Views - Last Post: 19 June 2009 - 06:55 PMRate Topic:     //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=110933&amp;s=c33497560ccda75b1acd916153fe4117&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ericr2427 Reputation: 40
• Posts: 378
• Joined: 01-December 08

# Finding primes optimization

Posted 19 June 2009 - 06:05 PM

Yes, I know this doesn't go here, but I put it here because it wasn't getting any attention in the C++ forum and technically it's not a problem with the programming, but with the logic. I was reading about how wheel factorization can be applied before a sieve of Eratosthenes to speed it up, so I wrote a program to do that.
```#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.

Is This A Good Question/Topic? 0

## Replies To: Finding primes optimization

### #2 firebolt Reputation: 93
• Posts: 5,561
• Joined: 20-February 09

## Re: Finding primes optimization

Posted 19 June 2009 - 06:41 PM

I think there may be a tutorial on a topic like yours. Have a look and maybe you'll find the logical error. ### #3 ericr2427 Reputation: 40
• Posts: 378
• Joined: 01-December 08

## Re: Finding primes optimization

Posted 19 June 2009 - 06:55 PM

There's no logical error, it's just taking way longer than I think it should take, and that there is a more efficient way to do that function.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }