@1waffle1 The method of only looking at odd numbers can be extended arbitrarily, too. (I think it ends up looking like the Sieve of Eratosthenes)

Consider numbers modulo 6:

if 0 mod 6, no good -- divisible by 6

if 2 mod 6, no good -- divisible by 2

if 3 mod 6, no good -- divisible by 3

if 4 mod 6, no good -- divisible by 2

Thus, we can do this

```
local primes = {2, 3, 5}
for i = 6, math.huge, 6 do
check(i + 1)
check(i + 5)
```

This is even faster: we check 33% of numbers instead of 50% of numbers!

You can go higher by multiply the first few primes together; Let `N = 2 * 3 * 5 = 30`

.

- 0 mod 30 no good
- 2 mod 30 no good
- 3 mod 30 no good
- 4 mod 30 no good
- 5 mod 30 no good
- 6 mod 30 no good
- 8 mod 30 no good
- 9 mod 30 no good
- 10 mod 30 no good
- 12 mod 30 no good
- 14 mod 30 no good
- 15 mod 30 no good
- 16 mod 30 no good
- 18 mod 30 no good
- 20 mod 30 no good
- 21 mod 30 no good
- 22 mod 30 no good
- 24 mod 30 no good
- 25 mod 30 no good
- 26 mod 30 no good
- 27 mod 30 no good
- 28 mod 30 no good

(Notice the only ones that are possibly prime are of the form `30 + p`

where `p`

is 1, or a prime between 5 and 30)

The above statement is sloppy as 1waffle1 pointed out. Really, `p`

must be *relatively prime* to `30`

, which is a much weaker property than primality. Since the smallest non-prime that's relatively prime to `30`

is `7 * 7`

, all of the numbers in the above list are prime, but in general that's not the case.

Thus we could start

```
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
for i = 30, math.huge, 30 do
check(i + 1)
check(i + 7)
check(i + 11)
check(i + 13)
check(i + 17)
check(i + 19)
check(i + 23)
check(i + 29)
```

Now we're only checking 26% of numbers -- even better!

However, the product `N = p_1 * p_2 * p_3 * ... * p_k`

grows very quickly.

For the first ten primes, `N`

would be `6,469,693,230`

. Thus for every six billion numbers, only several million will have to be checked. However, this only tells you how to find primes *larger* than 6 billion.