I have decided to take this quest a little further.Īfter some careful examination of the repeated crossings I have come to the awareness of the fact that, by the exception of i = 1 case, if either one or both of the i or j index value is among 4,7,10,13,16,19. So one idea might be segmentation and to keep n small all the time. Which means a further optimization of SoS bears the potentital to obtain the results even faster as n grows. The redundancy is around 20% for n = 100 however it increases to ~300% for n = 10M. i j vĪmong which there are only 5 duplicates. So clearly, this algorithm shouldn't be considered as an O(n^2) time complexity one. For instance for n = 50 (to check for primes up to 100) instead of doing 50 x 50 = 2500, we will do only 30 iterations in total. While this will not completely remove the redundant crossings it will 'greatly' eliminate the redundancy. Since we know that i + j + 2ij = n, this can easily be calculated as u = (n-i)/(1+2*i) J) The inner loop index j should start from i and run up to the point it can go with the current i value. We can easily solve the positive value for i by using the quadratic formula and that is the line with t = (Math.sqrt(4+8*n)-2)/4, I) So we have to find the the max value i and j can take when they are equal. As we need i and j values to calculate the numbers to cross out, i + j + 2ij up to n let's see how we can approach.

Sieve of Sundaram is only fast if the loop indices start and end limits are correctly selected such that there shall be no (or minimal) redundant (multiple) elimination of the non-primes. It's proof is beautifully explained here. The final stage is in fact the auto discounting of the even numbers. Once we cross out every i + j + 2ij, the remaining numbers are doubled and oddified (2n+1) to reveal a list of prime numbers. To select which integers to cross out the rule is i + j + 2ij ≤ n where i and j are two indices and n is the number of the total elements. Just like the Sieve of Erasthotenes, the Sieve of Sundaram algorithm also crosses out some selected integers from the list.

List of prime number to 100