# Prime Checker

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:

This algorithm can detect pseudoprimes, even the strongest ones:

Source

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

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

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

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.

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

Okay, whatever.