Just a bit of number theory... :) ------------------------------------- *** SEE THE EVEN FASTER NEW REMIIX: http://scratch.mit.edu/projects/20797789/ ------------------------------------- A remix to speed up the original (a lot! -though it doesn't create the list of composite numbers). Also, to show how the number of primes found up to the value entered compares to the prediction from the (slightly modified) prime number theorem. It can find the 78498 primes up to a million in about a minute. A lot of the speed-up comes from only checking up to the square root of each number being tested, as well as using non-refresh blocks. However, it also uses a couple of other tricks: 1. Checking only certain forms of number (ignoring others that cannot be prime - in particular, multiples of 2, 3, or 5); 2. Checking a load of numbers at the same time for a specific prime divisor, and eliminating any which are not prime, then adding those which remain after all prime divisors were checked. See inside for lots of comments... :) *** SEE THE EVEN FASTER NEW REMIX, which uses a sieve-based method, as I discuss below... In theory, a sieve method could be quicker. Unfortunately, Scratch's list operations (delete, insert & replace) are quite slow - only "add" is very fast. Adding is so much faster that it can even mean that replacing a load of items in a list can often be done more quickly by using only "add" operations into a second list, instead of using "replace" or "insert" within the same list (i.e. by copying the whole list elsewhere, with the modified values being added instead of the original, and then copying that whole list back into the one you really wanted it in!)
