trouble is with this approach to find all the primes smaller than 2 million it takes 45 seconds without stopping once past the square root of the number being tested. with an extra if statement to limit the search to a maximum of the square root of the number whole thing now takes 0.36 125 times faster!!
Last edited by cooper1200; 06-06-2019 at 02:58 PM.
For finding primes I have 2 ways - I ALWAYS use a sieve first.
This is because you only have to check each number once at the start (without division) and then you just use a lookup table, and you don't end up with a loop in a loop
The other (for large numbers) is - Check if even, and then a for loop that starts at 3, only checks odd numbers, and only checks divisors up to the square root of that number.
The problem is when you use this method as a "IsPrime()" in another loop - It has to go through the inner loop for every number.
For proof, solve a project Euler question with one method, and then the other.
either way you end up using huge dollops of memory to store the numbers generated
If you want speed, there is no way to avoid this...Originally Posted by cooper1200
The "for" loop does not use lots of memory, because it is checking on-the-fly, but it is very slow.
The sieve is fast but needs a lot of memory
either way if you are going to check for prime by dividing by primes you need a way to store the ones you have found. my arrays were getting close to 500000 elements each the size of int so nigh on 2mb
If you divide by all odd numbers (like I do) you don't need to store the primes. The idea of this method is to not take up memory, so you comprise on run time
Today it will be fun and possible to have fun,running two or more threads test primes with different algos
you tell me you can C,why dont you C your own bugs?
I am trying a vector approach
you tell me you can C,why dont you C your own bugs?
