 <p>Well some basic hints :</p> <ul> <li>do not use cout if not necessary.</li> <li>multiplication costs a lot. avoid unnecessary ones. For example use variables to store x*x, 4*x*x and 3*x*x outside of the y for loop. x*x is constant in the y for loop :) You even do 3*x*x 2 times in the y loop :)</li> <li>Store y*y in a variable too. Do not calculate it more than one time :)</li> <li>simplify flipPrime : just use isPrime[prime] = !isPrime[prime] without function call and if / else</li> </ul> <p>A lot more to be said. But try to do simple things first :) Then you can begin to read advanced article about loop unrolling and the rest.</p> <p>EDIT:</p> <p>As said in some comments, your compiler should optimize out some or all things I have pointed out. One can even argues that doing too many specific optimizations can be counter produtive as it might impair the compiler optimization capabilities. </p> <p>So one basic advice : - mesure the perfs of your initial algorithm - do one possible optimization - mesure the gain</p> <p>This way you will learn a lot about your compiler automatic optimization :)</p> <p>EDIT 2:</p> <p>As said in comments, my ubuntu 64bit with 4Gbytes RAM refuse to allocate the vector :) With a more reasonable billion limit, time give about 14 seconds. removing cout just gain about a second.</p> <p>As andreas said, the problem is the storage of the result. you have to store the inner loop result on disk !</p> <p>my 2 cents</p>