Is there a way to make this faster?

[MikeStgt]

I migrated following from REXX. As I am new to C++ my question is, if there is a chance to speed it up?

/* Sieve of Sundaram */
#include <iostream>		/* cout, cin, endl */
#include <ctime>		/* clock */
using namespace std;

unsigned long const o(100000000);
bool p[o] =  { };

int main()
{
	unsigned long i, j, k, n, z;

	clock_t t0 = clock();		/* time(R) */
	z = o / 2;
	for (j = 1; j <= (z-1)/3; ++j)
	{
		k = 2*j + 1;
		i = j;
		for (n = j + k; i > 0 && n <= z; (i--, n+=k))
			p[n] = true;
	}
	double te = (double)( clock() - t0 ) / CLOCKS_PER_SEC;  /* time(E) */
	n = 1;  // this is for the 2
	for (i=1; i <=z; ++i)
		if (!p[i])
			n++;
	cout << "From 1.." << o << " found " << n << " primes in " << te << " seconds." << endl;
}

Elapsed time is for sieving only, not for counting the primes.

[jonnin]

Read this thread, its an ongoing fun/contest for speeding up the sieve.

http://www.cplusplus.com/forum/beginner/250568/

[MikeStgt]

Just replacing array by vector results in a runtime reduction from 1.8 to 0.8 seconds (best time). No gain by rewriting the inner for loop, nothing but reduced readability. In contrast to S. of Eratosthenes when sieving up to n here only an array (now vektor) of size (n/2 + 1) is necessary.

/* Sieve of Sundaram */
#include <iostream>		/* cout, cin, endl */
#include <ctime>		/* clock */
#include <vector>
using namespace std;

unsigned long const o(100000000 / 2);
vector<bool> p(o+1, true);

int main()
{
	unsigned long i, j, k, n;

	clock_t t0 = clock();		/* time(R) */
	
	for (j = 1; j <= (o-1)/3; ++j)
		for ((k = 2*j + 1, n = j + k, i = j); i > 0 && n <= o; (p[n] = false, i--, n+=k));
	
	double te = (double)( clock() - t0 ) / CLOCKS_PER_SEC;  /* time(E) */
	
	n = 1;  // this is for the 2
	for (i=1; i <=o; ++i)
		if (p[i])
			n++;
	cout << "From 1.." << o+o << " found " << n << " primes in " << te << " seconds (sieving only)." << endl;
}