Prime Sieve
A prime sieve is a way to find prime numbers faster than just testing every number to see if it is divisible.
This is done by remembering all the prime numbers found already, and only testing those, since if a number is divisible by 4, it's divisible by 2. Furthermore, you only need to test numbers up to the square root of the number you're testing.
Example:
2 is prime.
sqrt(3) is less than 2, it's prime too.
sqrt(4) = 2, not prime
sqrt(5) < 3; 5 is not divisible by 2, prime (2 3 5)
sqrt(6) < 3; divisible by 2, not prime.
sqrt(7) < 3; 7 not divisible by 2, prime.
So now you can see that testing if 7 is prime only takes a square root function and one division by 2, instead of testing 7 vs 2, 3, 4, 5, and 6. This technique really starts paying off once you get into larger numbers and really start skipping more numbers.
I've used this approach multiple times in Project Euler, since many of the problems deal with prime numbers.
This is done by remembering all the prime numbers found already, and only testing those, since if a number is divisible by 4, it's divisible by 2. Furthermore, you only need to test numbers up to the square root of the number you're testing.
Example:
2 is prime.
sqrt(3) is less than 2, it's prime too.
sqrt(4) = 2, not prime
sqrt(5) < 3; 5 is not divisible by 2, prime (2 3 5)
sqrt(6) < 3; divisible by 2, not prime.
sqrt(7) < 3; 7 not divisible by 2, prime.
So now you can see that testing if 7 is prime only takes a square root function and one division by 2, instead of testing 7 vs 2, 3, 4, 5, and 6. This technique really starts paying off once you get into larger numbers and really start skipping more numbers.
I've used this approach multiple times in Project Euler, since many of the problems deal with prime numbers.
