Prime numbers array (C++)

Question

Hello! When trying to solve more complicated problem, I wrote some prime numbers generator calculating given amount of prime numbers (variable howMany). In SL Playground it gives "Time limit exceeded" error, but it seems to work. On CodeBlocks on my PC it works for 1017 first primes. If someone could look at the code and give the impression, and help to make it more efficient, and maybe not so complicated, I will by more than happy.
https://code.sololearn.com/cendkvb0i5GM

Answer 1

Pio I don't have code ready with me but below are few algorithm:

1. check from 2 to n and try to find mod of n with each number.. if modulo is zero, it is not prime..

2. rather than going from 2 to n, iterate till n/2 only

3. rather than going from 2 to n,
iterate till square root of n only

4. check for module by prime numbers only below n... for example, 15 is the case, just check with 2,3,5,7,11,13( primes below 15)

P.S. : algorithm 2 is more efficient than 1. 3 is more efficient than 2 and so on...

As you are already storing prime numbers, just check with algorithm 4 once...

Answer 2

https://code.sololearn.com/cGeRY6J2qLPJ/?ref=app Optimization and code complexity is very important and interesting part of coding. My version is able to calculate for 65536 limit, but unable to print them in time limit.
1. You should check only primes as delimiters, don't spend time to combined numbers.
2. If you didn't find small prime delimiter and square of current one is great then your number it means that there's no prime delimiters and you found a new one.
3. vector reallocate memory when it grows. Using list or set is faster when you not need in the random access.

Answer 3

In my opinion is way more confortable to use std::vector to handle all the primes numbers. I dont completely understand your intention with that if statementwith sqrt but I am not sure if that is really necessary

I wrote some code that may help you. You can ask if something is not clear :)

https://code.sololearn.com/cae3rn7Ns0G4/#cpp

Answer 4

Thanks for answers! i have some background in math and physics, but I'm a beginner in coding, so every remark is valuable. I didn't now about the vectors! What a shame!
@Ruben: Your code is nice. Sqrt is necessary as there is no need to check divisors until n/2, only to sqrt(n). Try to change this, it will run faster and use less memory!
@Sergey: Your code is awesome and the best! In Visual Studio it works up to 10000000 (10 milions!). It worked as long as 6 minutes 34 second, used 43 MB of memory and printed 664579 primes! The last ten primes are: "9999889, 9999901, 9999907, 9999929, 9999931, 9999937, 9999943, 9999971, 9999973, 9999991" Check it out yourself!
@Ketan: These steps are exactly what I intended to do. First to check divisors only to sqrt of the checked number, second to check divisors only from array, ie. they are prime numbers. I also made some optimisation by incrementing the checked value not by 1, but by 2 - every prime number larger that 2 is odd, so this is no use in checking even numbers. This is why I also added two first primes in the array - 2 and 3.
And the lesson I learned: always code in Visual Studio or Code::Blocks, use playground only for sharing the code.

Answer 5

Skipping odd numbers removes one hard division per iteration. It is cool but not great. 2 is the first prime number and it is checked at the first.
I replaced set by list in my example. It should increase performance by eliminating ln(n) cost of insert operation.