Prime Checker

Share your Projects
1

This is a block you can use to check if a number is prime, using a fast and reliable algorithm. This can check on a positive integer greater than 1 and works with BigNums too! These are some demonstrations:



untitled script pic - 2022-07-12T185041.313

This algorithm can detect pseudoprimes, even the strongest ones:


Source

Algorithm: https://www.researchgate.net/figure/Miller-Rabin-algorithm_fig1_297896849

1284×4962 1.15 MB

Copy and Import:

<blocks app="Snap! 7, https://snap.berkeley.edu" version="2"><block-definition s="is %&apos;n&apos; prime?" type="predicate" category="operators"><comment w="357.37109375" collapsed="false">Checks if a number is a prime.&#xD;This uses AKS-Miller-Rabin primality test, which is an improvement of AKS primality test. The algorithm is fast, with polinomial-time, probablistic, near to 0% error of choosing a composite one, and practical. Compatible with BigNums&#xD;&#xD;Sources: https://www.researchgate.net/figure/Miller-Rabin-algorithm_fig1_297896849</comment><header></header><code></code><translations></translations><inputs><input type="%n"></input></inputs><script><block s="doIf"><block s="reportIsA"><block var="n"/><l><option>list</option></l></block><script><block s="doReport"><block s="reportMap"><block s="reifyPredicate"><autolambda><custom-block s="is %n prime?"><l></l></custom-block></autolambda><list></list></block><block var="n"/></block></block></script><comment w="80" collapsed="true">Hyperization of function.</comment></block><block s="doIf"><block s="reportNot"><block s="reportIsA"><block var="n"/><l><option>number</option></l></block><comment w="80" collapsed="false">Error handlers.</comment></block><script><block s="doApplyExtension"><l>err_error(msg)</l><list><block s="reportJoinWords"><list><l>expecting a number but getting a </l><block s="reportTypeOf"><block var="n"/></block></list></block></list></block></script></block><block s="doIf"><block s="reportOr"><block s="reportLessThan"><block var="n"/><l>2</l></block><block s="reportNot"><block s="reportIsIdentical"><block s="reportMonadic"><l><option>floor</option></l><block var="n"/></block><block var="n"/></block></block></block><script><block s="doApplyExtension"><l>err_error(msg)</l><list><l>number is not an integer greater than 1</l></list></block></script></block><block s="doIf"><block s="reportOr"><block s="reportAnd"><block s="reportGreaterThan"><block var="n"/><l>93000000</l></block><block s="reportEquals"><block s="reportPower"><l>10</l><l>309</l></block><block s="reportPower"><l>10</l><l>310</l></block></block></block><block s="reportAnd"><block s="reportEquals"><block var="n"/><l>Infinity</l></block><block s="reportEquals"><block s="reportStringSize"><block var="n"/></block><l>8</l></block></block></block><script><block s="doApplyExtension"><l>err_error(msg)</l><list><l>number too large to process</l></list></block></script></block><block s="doDeclareVariables"><list><l>a</l><l>b</l><l>c</l><l>d</l><l>e</l><l>f</l><l>g</l></list><comment w="90" collapsed="false">Initialize variables.</comment></block><block s="doSetVar"><l>a</l><block s="reportNewList"><list><l>2</l></list></block><comment w="181" collapsed="false">Simple prime numbers generator:&#xD;https://scratch.mit.edu/projects/2740236</comment></block><block s="doSetVar"><l>b</l><l>3</l></block><block s="doSetVar"><l>c</l><l>1</l></block><block s="doWarp"><script><block s="doRepeat"><l>50</l><script><block s="doSetVar"><l>d</l><block s="reportMonadic"><l><option>sqrt</option></l><block var="b"/></block></block><block s="doUntil"><block s="reportOr"><block s="reportGreaterThan"><block s="reportListItem"><block var="c"/><block var="a"/></block><block var="d"/></block><block s="reportEquals"><block s="reportModulus"><block var="b"/><block s="reportListItem"><block var="c"/><block var="a"/></block></block><l>0</l></block></block><script><block s="doChangeVar"><l>c</l><l>1</l></block></script></block><block s="doIf"><block s="reportGreaterThan"><block s="reportListItem"><block var="c"/><block var="a"/></block><block var="d"/></block><script><block s="doAddToList"><block var="b"/><block var="a"/></block></script></block><block s="doChangeVar"><l>b</l><l>2</l></block><block s="doSetVar"><l>c</l><l>2</l></block></script><comment w="121" collapsed="false">Test first prime numbers. Recommended: 38 primes</comment></block><block s="doIf"><block s="reportListContainsItem"><block var="a"/><block var="n"/></block><script><block s="doReport"><block s="reportBoolean"><l><bool>true</bool></l></block></block></script><comment w="90" collapsed="false">Any number from the list is prime.</comment></block><block s="doIf"><block s="reportListContainsItem"><block s="reportAtomicMap"><block s="reifyReporter"><autolambda><block s="reportModulus"><block var="n"/><l></l></block></autolambda><list></list></block><block var="a"/></block><l>0</l></block><script><block s="doReport"><block s="reportBoolean"><l><bool>false</bool></l></block></block></script><comment w="164" collapsed="false">Numbers that are multiple of any number from the list are composite.</comment></block><block s="doSetVar"><l>b</l><l>0</l></block><block s="doSetVar"><l>c</l><block s="reportDifference"><block var="n"/><l>1</l></block></block><block s="doUntil"><block s="reportEquals"><block s="reportModulus"><block var="c"/><l>2</l></block><l>1</l></block><script><block s="doSetVar"><l>c</l><block s="reportMonadic"><l><option>floor</option></l><block s="reportQuotient"><block var="c"/><l>2</l></block></block></block><block s="doChangeVar"><l>b</l><l>1</l></block></script><comment w="94" collapsed="false">Write the number as 2^b*c+1 with c odd.</comment></block><block s="doSetVar"><l>a</l><block s="reportCDR"><block s="reportReshape"><block var="a"/><list><l>6</l></list></block></block><comment w="139" collapsed="false">Loop primes with powers of 2. Recommended: 6 &lt; 2*#primes</comment></block><block s="doSetVar"><l>d</l><l>4</l></block><block s="doSetVar"><l>e</l><l>1</l></block><block s="doUntil"><block s="reportLessThan"><block s="reportDifference"><block s="reportListAttribute"><l><option>length</option></l><block var="a"/></block><l>1</l></block><block var="e"/></block><script><block s="doUntil"><block s="reportOr"><block s="reportGreaterThan"><block s="reportListItem"><block var="e"/><block var="a"/></block><block var="d"/></block><block s="reportLessThan"><block s="reportListAttribute"><l><option>length</option></l><block var="a"/></block><block var="e"/></block></block><script><block s="doChangeVar"><l>e</l><l>1</l></block></script></block><block s="doIf"><block s="reportGreaterThanOrEquals"><block s="reportListAttribute"><l><option>length</option></l><block var="a"/></block><block var="e"/></block><script><block s="doInsertInList"><block var="d"/><block var="e"/><block var="a"/></block></script></block><block s="doSetVar"><l>d</l><block s="reportVariadicProduct"><list><block var="d"/><l>2</l></list></block></block><block s="doChangeVar"><l>e</l><l>2</l></block></script></block><block s="doRepeat"><l>20</l><script><block s="doSetVar"><l>d</l><block s="reportRandom"><block s="reportListItem"><l><option>last</option></l><block var="a"/></block><block s="reportDifference"><block var="n"/><l>1</l></block></block><comment w="158" collapsed="false">Pick random integer between the next prime/power of 2 and n - 1.</comment></block><block s="doDeleteFromList"><l><option>last</option></l><block var="a"/></block><block s="doForEach"><l>i</l><block var="a"/><script><block s="doSetVar"><l>e</l><block var="i"/></block><block s="doSetVar"><l>f</l><block var="n"/></block><block s="doUntil"><block s="reportEquals"><block var="e"/><l>0</l></block><script><block s="doSetVar"><l>g</l><block s="reportModulus"><block var="f"/><block var="e"/></block></block><block s="doSetVar"><l>f</l><block var="e"/></block><block s="doSetVar"><l>e</l><block var="g"/></block></script></block><block s="doIfElse"><block s="reportEquals"><block var="f"/><l>1</l></block><script><block s="doSetVar"><l>e</l><block s="reportDifference"><block var="i"/><block var="d"/></block></block><block s="doSetVar"><l>f</l><block s="reportDifference"><block var="n"/><l>1</l></block></block><block s="doSetVar"><l>g</l><l>1</l></block><block s="doUntil"><block s="reportEquals"><block var="f"/><l>0</l></block><script><block s="doIf"><block s="reportEquals"><block s="reportModulus"><block var="f"/><l>2</l></block><l>1</l></block><script><block s="doSetVar"><l>g</l><block s="reportModulus"><block s="reportVariadicProduct"><list><block var="g"/><block var="e"/></list></block><block var="n"/></block></block></script></block><block s="doSetVar"><l>f</l><block s="reportMonadic"><l><option>floor</option></l><block s="reportQuotient"><block var="f"/><l>2</l></block></block></block><block s="doSetVar"><l>e</l><block s="reportModulus"><block s="reportPower"><block var="e"/><l>2</l></block><block var="n"/></block></block></script></block><block s="doIf"><block s="reportNotEquals"><block var="g"/><l>1</l></block><script><block s="doReport"><block s="reportBoolean"><l><bool>false</bool></l></block></block></script></block></script><script><block s="doReport"><block s="reportBoolean"><l><bool>false</bool></l></block></block></script></block><block s="doSetVar"><l>d</l><l>1</l><comment w="85" collapsed="false">Miller-Rabin base.</comment></block><block s="doSetVar"><l>e</l><block var="d"/></block><block s="doSetVar"><l>f</l><block var="c"/></block><block s="doUntil"><block s="reportEquals"><block var="f"/><l>0</l></block><script><block s="doIf"><block s="reportEquals"><block s="reportModulus"><block var="f"/><l>2</l></block><l>1</l></block><script><block s="doSetVar"><l>d</l><block s="reportModulus"><block s="reportVariadicProduct"><list><block var="d"/><block var="e"/></list></block><block var="n"/></block></block></script></block><block s="doSetVar"><l>f</l><block s="reportMonadic"><l><option>floor</option></l><block s="reportQuotient"><block var="f"/><l>2</l></block></block></block><block s="doSetVar"><l>e</l><block s="reportModulus"><block s="reportPower"><block var="e"/><l>2</l></block><block var="n"/></block></block></script></block><block s="doIf"><block s="reportAnd"><block s="reportNotEquals"><block var="d"/><l>1</l></block><block s="reportNotEquals"><block var="d"/><block s="reportDifference"><block var="n"/><l>1</l></block></block></block><script><block s="doSetVar"><l>e</l><l>0</l></block><block s="doUntil"><block s="reportOr"><block s="reportGreaterThan"><block var="e"/><block s="reportDifference"><block var="b"/><l>1</l></block></block><block s="reportEquals"><block var="d"/><block s="reportDifference"><block var="n"/><l>1</l></block></block></block><script><block s="doSetVar"><l>d</l><block s="reportModulus"><block s="reportPower"><block var="d"/><l>2</l></block><block var="n"/></block></block><block s="doIf"><block s="reportEquals"><block var="d"/><l>1</l></block><script><block s="doReport"><block s="reportBoolean"><l><bool>false</bool></l></block></block></script></block><block s="doChangeVar"><l>e</l><l>1</l></block></script></block><block s="doIf"><block s="reportLessThan"><block var="d"/><block s="reportDifference"><block var="n"/><l>1</l></block></block><script><block s="doReport"><block s="reportBoolean"><l><bool>false</bool></l></block></block></script></block></script></block></script><comment w="131" collapsed="false">Improved AKS primality test.</comment></block></script><comment w="144.00000000000045" collapsed="true">Initialize rounds and algorithms. Recommended: 20</comment></block></script></block><block s="doReport"><block s="reportBoolean"><l><bool>true</bool></l></block><comment w="135" collapsed="false">If number have passed all the tests, it should be a prime.</comment></block></script></block-definition></blocks>

(C) 2022 ScratchModification

2

There has to be some way to make that code more readable by putting separable parts in subprocedures!

3

Why? You can check the original algorithm and its procedures.

4

If you don't want to make it readable, that's fine. I guess people who grew up with Scratch before it had custom blocks learned to fight their way through huge long scripts. But I can't do it.

5

Huh... I discovered Scratch in 2018. At that time there were custom blocks and I really liked to make them.
I just don't want that blocks to depend on other blocks, to be independent and run without defining more blocks

6

Okay, whatever.