LOVE, FAVE, FOLLOW, COMMENT! This is the Euler's sieve to get all primes within a linear time. Unfortunately, since scratch can't create lists longer than 200000 items, it can only generate primes within 200000. (which is the first 17984 of them) If you want to restrict the maximum prime, restrict the length of the "is prime?" list. (It lengthens automatically in this project) ------------------------------------ Speed test (1000 primes, no turbo): Euler's sieve: 23.826 seconds. The normal algorithm: 295.865 seconds. (12.5 times slower!) Speed test (5 minutes, no turbo): Euler's sieve: 4,338 primes. (4.15 times more!) The normal algorithm: 1,045 primes.
Idea from Euler(1707-1783), the great mathematician. This is an improvement for @zuocr 's https://scratch.mit.edu/projects/381255173/ Probably will also implement Miller-Rabin someday. UPD: I will implement it if it reaches 10 loves or 10 faves! ------------------------------------ #number #numbers #math #mathematics #numbertheory #prime #primes
