Recently, I release my recent version of my Useful Custom Blocks project, v1.2 (see here). One of the blocks I decided to include was a block that said “is (num) prime?”. (The answer is output to a variable, since we only have stack/rectangular custom blocks at the moment).

So, I included my own custom-made algorithm to test it, which you can see in the project. The information I used for it came from here. Here's the basic set of logic for it:

- check if the number is an integer greater than one - if not, automatically false
- assume the number is true (in case nothing else happens to change the output variable in the script)
- check if the number is divisible by 2 or 3 and is not two or three - if so, automatically false
- finally, check if the number is divisible by any numbers less than the square root of that number which follows the form 6k+1 or 6k-1 (ex. 5, 7, 11, 13, 17, 19…) - if so, then it's false*

*According to Wikipedia, all prime numbers greater than 3 follow the form 6k+1 or 6k-1 … so I use this to speed up the process, rather than just checking if the input number is divisible by /all/ odd numbers.

I'm wondering if anybody else has made scripts for this kind of thing, and if you have any suggestions for improving the algorithm.

Seems fine to me.

That looks like a decent method. And it's really compact and neat!

There are ways you could possibly make it a touch faster, using more complicated stuff - though it will also depend somewhat upon how quickly Scratch does certain things (processing lists, for example). And the scripting would not be anywhere near as tidy as you have it now, unfortunately.

One thing I would point out, more generally, is that I've noticed Scratch is significantly faster if you have a “repeat N” rather than “repeat until”. Presumably, it only has to interpret the count once in the first case, repeating the loop that many times. Whereas the second case it has to re-interpret the expression and test whether it's is true or not.

In the case of your prime test, for example (there are others where you can probably do this too), you could try working out just before the loop what value of “i” you need to first make 6i-1 > sqrt(num). Then you can repeat that many times, avoiding the “repeat until”.

Ideally, you'd also do “stop this script” when it finds a divisor (after “set output to false”). Unfortunately, I've noticed that's rather bugged in non-refresh blocks - it doesn't seem to stop if it's within a loop.

However, another thing I've found is that Scratch will do “repeat N” loops, that contain no kind of “wait” or screen changing blocks, all at once - as if non-refresh. This means you can probably switch off the non-refresh for such blocks (including the prime test), and it'll hopefully make no difference. -And “stop this script” might actually work, then…?

Hope those ideas are helpful!

1 isn't prime?

Indeed not - a prime is divisible by exactly two different integers: itself and one.
One is divisible by only a single integer: itself (which is also one…)

OK, so for various more technical explanations, see here: http://primes.utm.edu/notes/faq/one.html

Probably the most straightforward to understand why it's important is the “fundamental theorem of arithmetic”, which is to do with expressing an integer as a product of prime factors in a unique way…

See: http://en.wikipedia.org/wiki/Prime_number#Primality_of_one

DadOfMrLog wrote:

That looks like a decent method. And it's really compact and neat!

There are ways you could possibly make it a touch faster, using more complicated stuff - though it will also depend somewhat upon how quickly Scratch does certain things (processing lists, for example). And the scripting would not be anywhere near as tidy as you have it now, unfortunately.

One thing I would point out, more generally, is that I've noticed Scratch is significantly faster if you have a “repeat N” rather than “repeat until”. Presumably, it only has to interpret the count once in the first case, repeating the loop that many times. Whereas the second case it has to re-interpret the expression and test whether it's is true or not.

In the case of your prime test, for example (there are others where you can probably do this too), you could try working out just before the loop what value of “i” you need to first make 6i-1 > sqrt(num). Then you can repeat that many times, avoiding the “repeat until”.

Ideally, you'd also do “stop this script” when it finds a divisor (after “set output to false”). Unfortunately, I've noticed that's rather bugged in non-refresh blocks - it doesn't seem to stop if it's within a loop.

However, another thing I've found is that Scratch will do “repeat N” loops, that contain no kind of “wait” or screen changing blocks, all at once - as if non-refresh. This means you can probably switch off the non-refresh for such blocks (including the prime test), and it'll hopefully make no difference. -And “stop this script” might actually work, then…?

Hope those ideas are helpful!

Thanks for the feedback.

I see what you mean regarding the “repeat until” blog being slower - although I haven't noticed the difference before, and I'm not totally sure how much of a difference it would make. And I'm not sure where I would start as far as calculating how many times I would have to loop. I mean, the first point when the “divisible by 6k +/- 1” rule comes into play is around 25 I think (until then, all of the numbers are divisible by two or three or are prime).

However I did take your advice about non-refresh blocks and changed the scripts to allow screen refreshing (as well as adding the stop script block). Hopefully that will improve efficiency.

P.S. Yeah, speaking of the primality of one, on one of the math tests I had this year, there was a problem about logic / determining patterns, which included (what was supposed to be) a list of prime numbers, except it had 1 in it. That made me think it wasn't a prime list, so I was trying to figure out the pattern, but I couldn't figure anything out, so I gave some kind of dummy answer. Eventually the tests were given back and quite a few kids had the same thought as mine about the problem, but the teacher claimed one was prime! I was a bit annoyed (since she arguably shouldn't take points off for a faulty problem), but oh well. Arguing with teachers isn't always the best option. xD But I guess it takes time for the knowledge to spread around, eh?

This can be adapted. it is very efficient. http://scratch.mit.edu/projects/10991473

There is also another method:

Check all primes under the square root of the given number…
of course, that arises problems itself such as looking for prime numbers under the square root…

A method to find prime numbers is that take a number example 5 and the prime numbers before it and divide it like 5/3 and 5/2 so if it is divisible by any of them except itself then it's not a prime number if 5 is not divisible by 3 or 2 then it is prime. And as we know 5 is a prime number.

This is a very interesting topic that I'm trying to figure out.

Challenge: Can anyone make a project in scratch that finds prime numbers?

Amolv wrote:

Challenge: Can anyone make a project in scratch that finds prime numbers?

There are already several of these including one in my profile.

deck26 wrote:

Amolv wrote:

Challenge: Can anyone make a project in scratch that finds prime numbers?

There are already several of these including one in my profile.

Never Mind!

A good fast algorithm to check if a number is prime is

3^n-1 mod n

and if it equals 1 its prime. However, it has a small chance of mistaking a composite number for a prime.

ig7yofy

sionazo wrote:

ig7yofy

Please don't spam.

deck26 wrote:

sionazo wrote:

ig7yofy

Please don't spam.

Yeah, don't

You can try this:

Minecraft121LogonALT wrote:

You can try this:

You're responding to a very old topic. Also your method is very inefficient - you don't need to check up to answer/2, only up to sqrt(answer). For any number up to 100 you never need to check any divisor > 7 since 8, 9 and 10 are not prime and 0 = sqrt(100). For any divisor greater then the square root there must be a matching divisor which is less than the square root.

Topic closed due to necroposting.