# Number is a prime number - Challenge

## Recommended Posts

In the spirit of the >last challenge, here is a new one for the community.

Challenge: Create the smallest number of lines of AutoIt code to check if a number is a prime number e.g. 3, 7 or 11. You must include the ability to ask the user to enter a number and you're allowed to use UDFs. Also the use of /AutoIt3ExecuteScript is frowned upon and will not be accepted as a solution.

Good luck.

PS If you use someone else's code, then provide a link as to where you obtain it from, otherwise it's considered plagiarism in this challenge.

Edited by guinness

##### Share on other sites

```MsgBox(0, "Prime Check", IsPrime(InputBox("Prime Check", "Enter a number")))
Func IsPrime(\$n) ;sieve of Eratosthenes
\$n *= 1
If Not (\$n < 2 ? False : Not Mod(\$n, 2) ? False : Not IsInt(\$n) ? False : True) Then Return False
Local \$i
For \$i = 3 To Ceiling(Sqrt(\$n * 1)) Step 2
If Not Mod(\$n, \$i) Then Return False
Next
Return True
EndFunc```
Edit: added check for input whether it is an integer.

Br,

UEZ

Edited by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

Fixed.

Br,

UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

Surely not the most compact entry, but this one handles large inputs:

```#include <String.au3>
#include "..\Include\BigNum.au3"
Local \$Inp, \$bComposite
While 1
\$Inp = InputBox("Prime challenge", "Enter a positive number", "0")
If @error Then ExitLoop
\$Inp = StringRegExpReplace(\$Inp, "^(-?)0*(\d+)\$", "\$1\$2")
If StringLeft(\$Inp, 1) <> '-' Then
If StringLen(\$Inp) < 5 Then
\$Inp = Int(\$Inp)
\$bComposite = StringRegExp(_StringRepeat('1', \$Inp), '^1?\$|^(11+?)\1+\$')
Else
\$bComposite = _IsBigNumComposite(\$Inp)
EndIf
MsgBox(0, "Prime challenge", \$Inp & (\$bComposite ? " isn't" : " is") & " prime.")
EndIf
WEnd

Func _IsBigNumComposite(\$n)
If Mod(StringRight(\$n, 1), 2) = 0 Then Return True
Local \$n_1 = _BigNum_Sub(\$n, "1"), \$t, \$q = \$n_1, \$a, \$e, \$b, \$any
While Mod(StringRight(\$q, 1), 2) = 0
\$t += 1
\$q = _BigNum_Div(\$q, 2)
WEnd
For \$c = 1 To 10
\$a = String(Random(2, 100, 1))
\$b = __BigNum_PowerMod(\$a, \$q, \$n)
If \$b <> "1" Then
For \$e = 1 To \$t
If \$b = \$n_1 Then ContinueLoop
\$b = _BigNum_Mod(_BigNum_Mul(\$b, \$b), \$n)
Next
If \$b <> \$n_1 Then Return True
EndIf
Next
Return False
EndFunc

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_PowerMod
; Description ...: Modular Exponentiation Mod(\$n^\$e, \$k)
; Syntax.........: _BigNum_Pow(\$n, \$e, \$k)
; Parameters ....: \$n - Positive StringNumber: Digits"0"..."9"
;                  \$e - Positive StringNumber: Exponent
;                  \$k - Positive StringNumber: Modulus
; Return values .: Success - Result Mod(\$n^\$e, \$k)
;                  Failure - -1, sets @error to 1 if \$n is not a positive valid StringNumber
;                            -1, sets @error to 2 if \$e is not a positive valid StringNumber
;                            -1, sets @error to 3 if \$k is not a positive valid StringNumber
; Author ........: jchd
; Date ..........: 17.12.13
; Remarks .......: Fractional exponents not allowed - use BigNum_n_root instead.
; ;===============================================================================================
Func __BigNum_PowerMod(\$n, \$e, \$k)
If Not __BigNum_IsValid(\$n) Then Return SetError(1, 0, -1)
If Not __BigNum_IsValid(\$e) Then Return SetError(2, 0, -1)
If Not __BigNum_IsValid(\$k) Then Return SetError(3, 0, -1)
Local \$res = "1"
While \$e <> "0"
If Mod(StringRight(\$e, 1), 2) Then
\$res = _BigNum_Mod(_BigNum_Mul(\$res, \$n), \$k)
\$e = _BigNum_Sub(\$e, "1")
EndIf
\$n = _BigNum_Mod(_BigNum_Mul(\$n, \$n), \$k)
\$e = _BigNum_Div(\$e, "2")
WEnd
Return \$res
EndFunc   ;==>__BigNum_PowerMod```

Try it for instance with:

732948462788910564089061879048971 = 1321 * 5443 * 40154249 * 2538638012109604393

then:

732948462788910564089061879048973 (this one actually prime).

BigNum should be standard, BTW.

The threshold used to switch between the regexp and Miller-Rabin may not be optimal, but who cares?

EDIT: forgot to mention that the regexp comes from an old collection of Perl gems and possibly well before. The oldest trace I could locate is http://www.mit.edu:8008/bloom-picayune.mit.edu/perl/10138 but it doesn't seem to be alive, at least not from where I live.

Miller-Rabin is, well, Miller-Rabin test.

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

Less sophisticated than jchd's, but I might as well add my own. It's limited to 15 digits and uses a small sieve (static variable). I can't remember why I rejected using a larger sieve, but there was something about it.

##### Share on other sites

Darn it! jchd used the same/thing idea I had, but didn't post a link to the source of the regular expression.

```#AutoIt3Wrapper_Run_Au3Check=N
#include <String.au3> ; For _StringRepeat() only.
; Regular expression provided by http://montreal.pm.org/tech/neil_kandalgaonkar.shtml.
Local \$aArray = [InputBox('Enter a number', ''), MsgBox(4096, '', ((StringRegExp(\$aArray[0], '(?:^(?!^0+)\d+\$)') > 0) ? \$aArray[0] & ' is ' & ((StringRegExp(_StringRepeat('1', Int(\$aArray[0])), '^(1?|(11+?)\2+)\$') > 0) ? 'not' : '') & ' a prime number.' : 'Please enter a valid number.'))]```

I know precision is off when numbers get massive, but that wasn't the main goal of this challenge.

Edited by guinness

##### Share on other sites

I just added the link I found for the regexp, right before you frowned upon its absence!.

And I posted before the same Miller-Rabin >here and the regexp >here.

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

I see it now, thanks. I found it a while back by Robjong, so just searched the Forum and see it was a prime number question >> '?do=embed' frameborder='0' data-embedContent>>.

Edited by guinness

##### Share on other sites

That's it. I added my own links as well. It's funny that this use of backtracking nicely reminds of a recent discussion about regexp and the possibility of a stack overflow. Discussion now peacefully continued over MPs.

EDIT: I believe I found the first post of Abigail (well-known Perl hacker) in comp.lang.perl.misc having this (his) regexp in signature.

```Date: 16 Sep 1998 20:19:40 GMT
From: abigail@fnx.com (Abigail)
Subject: Re: how safe is xor encryption ?
Message-Id: <6tp6gs\$k0k\$1@client3.news.psi.net>

Elaine -HappyFunBall- Ashton (eashton@bbnplanet.com) wrote on MDCCCXLII
September MCMXCIII in <URL: news:360000B8.259600FD@bbnplanet.com>:
++ Mark-Jason Dominus wrote:
++
++ > If the key is intercepted, it is not very useful to the snooper.  They
++ > can use it to authorize purchases from you, but not from anyone else.
++
++ How so? If I can get the key, I can get the CC# and then I can make
++ purchases anywhere I want.

No. You need the key *and* the encrypted number.

++ > If the entire database is stolen, it is not useful to the thief
++ > without a database of decryption keys, and no such database exists.
++
++ You presume that the key length is sufficient to render the decryption
++ impractical or impossible. Also, too, that the customer has chosen a
++ totally random key which, in my experience at least, is all too rare an
++ occurance.

Impossible is the right answer. The beauty of XOR encryption is that even
if you brute force try all keys, and you hit the right one, you have
absolutely no idea it is the right key.

For instance, I might give you the encrypted text "t^R][S".  You might
try keys, and find out that XORring with "123456" gives "Elaine". However,
XORring with "5-:)4=" will give you "Ashton". And a key of "<?16>!" will
give you "Hacker". For any 6 character string, there will be a unique,
6 character key that, when applied to the encrypted text, gives you the
target text.

Abigail
--
perl -wle 'print "Prime" if (1 x shift) !~ /^1?\$|^(11+?)\1+\$/'

------------------------------```
Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

Done, and done (loop-hole):

```#include <IE.au3>
\$oIE = _IECreate("http://www.math.com/students/calculators/source/prime-number.htm",0,0)
\$oNumber = _IEGetObjByName(\$oIE,"number")
\$oButton = _IEGetObjByName(\$oIE,"button")
\$oResult = _IEGetObjByName(\$oIE,"result")
_IEFormElementSetValue(\$oNumber,\$i)
_IEAction(\$oButton,"Focus")
_IEAction(\$oButton,"Click")
MsgBox(1,1,_IEFormElementGetValue(\$oResult))
_IEQuit(\$oIE)```

Too bad it can't handle large numbers, cause it's quick

I was thinking of screen crawling|scraping other sites that list them all, up to the largest of numbers.  That would still be quicker than calculating it.

Or maybe even writing out all the primes to a file, and doing a lookup.  Keep writing until the user does the query....obviously, the more times, and longer able to write out, the quicker it will be.  if you have a full repo, then you only have to check that the number is not divisible by 2,3,5, and all the primes up to that point (of the ceiling of the square root of the number)

Edited by jdelaney

IEbyXPATH-Grab IE DOM objects by XPATH IEscriptRecord-Makings of an IE script recorder ExcelFromXML-Create Excel docs without excel installed GetAllWindowControls-Output all control data on a given window.

##### Share on other sites

You can as well use Wolfram Alpha and handle arbitrarily large integers by just asking:

http://www.wolframalpha.com/input/?i=is%20732948462788910564089061879048973%20prime

But relying on external computing power is just cheating.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

this is my solution

```MsgBox(0, "Prime Check", Prime(InputBox("Is this number prime?", "Enter an integer greater than 1")))
func prime(\$n)
local \$p=0
if \$n<=1 or (\$n-int(\$n))<>0 then Return "Your number is not valid"
for \$i=2 to \$n step 1
if isint(\$n/\$i) then \$p=\$p+\$i
next
if \$p=\$n Then Return "Your number is prime"
if \$p<>\$n Then Return "Your number is not prime"
EndFunc ```
Edited by Raizeno

##### Share on other sites

```MsgBox(0, "Prime Check", IsPrime(InputBox("Prime Check", "Enter a number")))
Func IsPrime(\$n) ;sieve of Eratosthenes
If Not (\$n < 2 ? False : Not Mod(\$n, 2) ? False : True) Then Return False
Local \$i
For \$i = 3 To Ceiling(Sqrt(\$n)) Step 2
If Not Mod(\$n , \$i) Then Return False
Next
Return True
EndFunc```
Br,

UEZ

your script will say fractions are prime numbers.

##### Share on other sites

Dont take this entry as being too serious but does one line count

`ShellExecute('http://www.onlineconversion.com/prime.htm')`

Carry on with the serious stuff now the obvious has been pointed out

Edited by Chimaera

If Ive just helped you ... miracles do happen. Chimaera

##### Share on other sites

No, see post #14.

I see next time I will be have to be even more specific when it comes to these AutoIt based challenges.

##### Share on other sites

your script will say fractions are prime numbers.

Fixed in post#2.

Br,

UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

On a side note: my code uses the largest step value I've ever used in a For loop - Step 30030. That maybe not big by some people's standards but I don't think it's so common. I had fun with it anyway.

## Create an account

Register a new account

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...