list of prime numbers till 100 shell script program

So let me introduce you the modified Sieve of Sundaram probably at it's best when not segmented. But that code will follow a little later. So that we will be able to use multiple threads too. I have also implemented the segmentation part of this algorithm to push to the workers. In the below modified algorithm, finding the primes up to 100M takes the same amount of time. In JS, just an empty loop counting up to 1B takes like 4000ms. So for instance for 1M integers the nested loop's total turn count dropped to like 1M from 1.4M. Then allowing the inner loop to turn only when i%3-1 != 0, a further cut down like 35-40% from the total number of the loops is achieved. series, a duplicate crossing is generated. 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 numbers till 100 shell script program