Making a little program faster

[pieroborrelli]

Hello, I started programming for the first time in my life about 2 months ago. I'm studying the C++ programming language using the book : Programming principles and practice using C++ and I would like to recieve an advice by you. In chapter 4 I had to write a program to find all the primes between 1 and 100 using the sieve of Eratosthenes so I wrote this program :

#include <iostream>
#include <vector>

using namespace std;

// find all the primes number using Eratosthenes
int main()
{

	vector<bool> numbers(101); 
	
	int counter = 2; 
	while (counter <= 11) {

		for (int i = counter; i < numbers.size(); ++i)	
			if (i != counter && i % counter == 0)	
				numbers[i] = 1; 

		++counter; 

	}

	for (int x = 0; x < numbers.size(); ++x)
		if (numbers[x] == 0 && x > 1)
			cout << x << " is a prime number\n"; 

}

This is the first time in my life (I'm 15) that I show my newbie code to someone, but my problem is that if I try to modify the program to find all the primes between 1 and max (setting the size of the vector uqual to max) my program becomes slower and I would like to listen by other people some possible solution to don't use vector in this program, is it possible ? Sorry but I'm hust a beginner and I know just a little bit of all the features of the C++ programming language, the author hasn't shown me yet how to delete a value from a vector so I just used this method to solve the problem, Thank you.

[MiiNiPaa]

1) console output is slow. Use std::cout.sync_with_stdio(false); to get 2x speedup on console IO.
2) Consider dumping output in files: this is way faster.

3) vector<bool> is optimised for space efficiency sacrificing speed.
This code:

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
    std::cout.sync_with_stdio(false);
    auto start = clock();
    vector<bool> numbers(10001);
    int counter = 2;
    while (counter <= numbers.size()) {

        for (int i = counter; i < numbers.size(); ++i)
            if (i != counter && i % counter == 0)
                numbers[i] = 1;

        ++counter;
    }
    auto end = clock();
    for (int x = 0; x < numbers.size(); ++x)
        if (numbers[x] == 0 && x > 1)
            cout << x << " is a prime number\n";
    std::cout << double(end-start) / CLOCKS_PER_SEC;
}

Gives me

1.315
Process returned 0 (0x0)   execution time : 1.405 s

When if I change vector<bool> to vector<int>:

0.259
Process returned 0 (0x0)   execution time : 0.356 s

When using raw arrays (or std::array):

0.215
Process returned 0 (0x0)   execution time : 0.313 s

As you can see, difference is neglible.
Also your sieve implementation is suboptimal. There is room for improvement.

[Computergeek01]

1) console output is slow. Use std::cout.sync_with_stdio(false); to get 2x speedup on console IO.

I wanted to point out that if you are running this app on a Windows platform, especially anything newer the XP, you may not see any much improvement in performance at all: http://en.wikipedia.org/wiki/Client/Server_Runtime_Subsystem .

[MiiNiPaa]

you may not see any improvement in performance at all

I use Win7 and generally have 2x speedup.

OP: I decided to test improved sieve vs your version:
I used 100001 as a size of working set. ()

your version:
25.449
Process returned 0 (0x0)   execution time : 25.458 s
Optimised:
0.003
Process returned 0 (0x0)   execution time : 0.013 s

So, optimise your algorithm.


EDIT: decided to play further. Working set of 10 000 001 numbers. I generated sieve, extracted primes into separate vector, printed them.
results:

Time spent on sieve generation: 0.336
Time spent on result extraction: 0.017
Time spent on output: 31.506

After replacing screen IO with files:

Time spent on sieve generation: 0.345
Time spent on result extraction: 0.017
Time spent on output: 0.098