# Thread: calculating if a number is a prime number or not

1. 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!! 2. 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. 3. either way you end up using huge dollops of memory to store the numbers generated 4. Originally Posted by cooper1200 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... 5. 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 6. 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 7. 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 8. Originally Posted by Click_here For finding primes I have 2 ways - I ALWAYS use a sieve first.
Today it will be fun and possible to have fun,running two or more threads test primes with different algos 9. I am trying a vector approach Popular pages Recent additions calculate, forward, number, prime, states 