ScratchData LogoScratchData
Back to scratchisthebest's profile

Fast Primality Test

SCscratchisthebest•Created May 3, 2011
Fast Primality Test
4
2
138 views
View on Scratch

Instructions

heh maybe i'll update this UPDATE 10/27/13: SUPER FASTER (doesn't bother adding even numbers to the list duh)

Description

This rather quick primer gives you ONLY prime numbers, fast! Give it a huge number and let it run all day, or give it a small number and get a list of primes smaller than it. Let me know if you see a composite number. :O HOW I MADE THIS I looked up a prime test on the internet. This is a very fast one, called Euler's Sieve or something like that. You take a lllooonnnggg list of numbers, and remove all multiples of the first number, then the second, then the third, and so on. TURNING IT INTO SCRATCH The ()mod() block returns the remainder of division. For example, 7 mod 2 is 1, because 7/2 is 3r1. So if the mod is zero, I know that the second number "goes into" the first. 6 mod 3 is 0 because 6 is a multiple of 3. So, since prime numbers have no divisors that are on the list of 2 to anything (except for themselves, which this dosen't test), and ()mod() is really a factor detector, I can detect primes quickly and easily! THINGS YOU CAN DO See if you can find a way to make it faster! This sometimes tries to find numbers in a list that aren't really there, because of how repeat() blocks work. See if you can remove those errors.

Project Details

Project ID1763502
CreatedMay 3, 2011
Last ModifiedOctober 27, 2013
SharedMay 3, 2011
Visibilityvisible
CommentsAllowed