Finding primes optimization

Need help with the math/logic of this

Page 1 of 1

2 Replies - 1157 Views - Last Post: 19 June 2009 - 06:55 PM Rate Topic: -----

#1 ericr2427   User is offline

  • D.I.C Regular
  • member icon

Reputation: 40
  • View blog
  • 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   User is offline

  • D.I.C Lover
  • member icon

Reputation: 93
  • View blog
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#3 ericr2427   User is offline

  • D.I.C Regular
  • member icon

Reputation: 40
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1