Sundaram's Sieve

Step 2 — Solution

Since N lies in the array, it is equal to (2n+1)m+n for some n and m. Use this to work out 2N+1 in terms of m and n:

2N+1=2[(2n+1)m+n]+1=2(2n+1)m+ 2n+1=(2n+1)(2m+1).

Since 2m+1 and 2n+1 are both integers greater than 1, this shows that 2N+1 has factors that are both greater than one, so it cannot be prime. This shows that if N lies in the array, then 2N+1 cannot be prime.

Got it, on to the next step;
Back to the main article