Number is a prime number - Challenge

[guinness]

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 October 11, 2014 by guinness

[UEZ]

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 October 12, 2014 by UEZ

[guinness]

Great, but you're missing the part to ask a user to enter a value.

[UEZ]

Fixed.

Br,

UEZ

[jchd]

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

expandcollapse popup

#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 October 11, 2014 by jchd

[guinness]

Great so far. I will hold off on a day or so before I post my solution.

[czardas]

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.

[guinness]

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 October 12, 2014 by guinness

[jchd]

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 October 11, 2014 by jchd

[guinness]

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 October 11, 2014 by guinness

[jchd]

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 October 11, 2014 by jchd

[jdelaney]

Done, and done (loop-hole):

#include <IE.au3>
$i = InputBox("add number", "enter your number")
$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")
_IELoadWait($oIE)
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 October 11, 2014 by jdelaney

[jchd]

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.

[guinness]

jdelaney,

You could have looked at the JavaScript code to convert to AutoIt.

[Raizeno]

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 October 12, 2014 by Raizeno

[Raizeno]

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.

[Chimaera]

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 October 12, 2014 by Chimaera

[guinness]

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.

[UEZ]

your script will say fractions are prime numbers.

Fixed in post#2.

Br,

UEZ

[czardas]

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.