_isprime Function

[jvanegmond]

It'd be interesting if someone were to look up and code a prime number generator that didnt use a brute force approach but an algorithm of some sort.

Look up 2 posts. Sieve of Eratosthenes.

[RazerM]

It'd be interesting if someone were to look up and code a prime number generator that didnt use a brute force approach but an algorithm of some sort.

Is that possible?

[jvanegmond]

Sieve of Eratosthenes is the only algorithm i know of. It's not like you can just multiply a number by 1.284924 or something.

Edited September 18, 2006 by Manadar

[RazerM]

Yes, i thought he meant like a function

$one_thousandth_prime = Prime(1000000)

[jvanegmond]

Brute force approach or algorithm?

Edited September 18, 2006 by Manadar

[Wus]

Well there is an nth term definition for prime numbers, however that is ridiculous and not somthing worth implementing. Ill link it if I can find it (internets not doing so hot atm). I meant something a lil more elegant than the sieve... Ill try to find some math to back up my fat mouth.

Edit:

My mouths fat...

http://en.wikipedia.org/wiki/Prime_Number_Theorem

http://en.wikipedia.org/wiki/Prime_number

There are ways of optimizing the sieve, and ways of finding primes that work within a certain domain, but thats seems like all.

Edited September 19, 2006 by Wus

[nfwu]

Hey, the prime number theorem only gives an approximate value of the number of primes below a certain number.

Read up on John Pollard's method in finding moderate-sized factors. I do not have any website on hand now but I do have a Number Theory book somewhere (I'm nuts about Maths). I'll look it up.

#)

[nfwu]

http://en.wikipedia.org/wiki/Pollard's_rho_algorithm

http://en.wikipedia.org/wiki/Integer_facto...ring_algorithms

#)

[The Kandie Man]

I wrote this a while back:

expandcollapse popup

;Prime Number Finder
;~ $numbertocalcto = 1000
#include <file.au3>

$comments = False

While 1
    $numbertocalcto = InputBox("Enter Number", "Enter a number integer that this program will calculate primes up to:")
    If IsInt(Number($numbertocalcto)) And $numbertocalcto > 2 Then ExitLoop
    $response = MsgBox(49, "Error!", "You didn't enter a valid number.  Please try again.")
    Select
        Case $response = 1 ;OK
        Case $response = 2 ;Cancel
            Exit
    EndSelect
WEnd

$counter = 1

$filename = "Prime to " & $numbertocalcto & " " & @Mon & "-" & @MDAY & "-" & @YEAR & ".txt"

_FileCreate($filename)

$h_filehandle = FileOpen($filename,1)

If $comments = True Then
ConsoleWrite("Prime Numbers Calculater to " & $numbertocalcto & @LF)
FileWrite($h_filehandle,"Prime Numbers Calculater to " & $numbertocalcto & @CRLF)

ConsoleWrite('Prime number # 1: ' & 2 & @LF)
FileWrite($h_filehandle,'Prime number # 1: ' & 2 & @CRLF)

Else
ConsoleWrite("Prime Numbers Calculater to " & $numbertocalcto & @LF)
FileWrite($h_filehandle,"Prime Numbers Calculater to " & $numbertocalcto & @CRLF)

ConsoleWrite(2 & @LF)
FileWrite($h_filehandle,2 & @CRLF)
    
Endif


For $Number = 3 to $numbertocalcto Step 2
    
    $divisor = 3
    While 1
        If $divisor * $divisor > $Number or Mod($Number,$divisor) = 0 Then Exitloop
        $divisor = $divisor + 2 
    Wend
    
    IF $divisor * $divisor > $number Then   ; are all divisor exhausted?
        $counter = $counter  + 1              ; yes, this Number is a prime
        If $comments = True Then
        ConsoleWrite('Prime number #' & $counter  & ': ' & $Number & @LF)
        FileWrite($h_filehandle,'Prime number #' & $counter  & ': ' & $Number & @CRLF)
        Else
        ConsoleWrite($Number & @LF)
        FileWrite($h_filehandle,$Number & @CRLF)
        Endif
    EndIf
    
Next
ConsoleWrite("There were " & $counter & " primes found between 2 and " & $numbertocalcto  & @LF )
FileWrite($h_filehandle,"There were " & $counter & " primes found between 2 and " & $numbertocalcto  & @CRLF )

FileClose($h_filehandle)

[darkshadow791]

I know this is fairly old but wouldn't this work?

Func _IsPrime($i_num)
    If Not IsInt($i_num) Then Return 0
    Local $Abs
    $Abs = Abs($i_num)
    If IsInt($Abs) Then
        Return 0
    EndIf
    Local $b = 0
    Local $a = 0
    Local $i_Abs = Ceiling($Abs) + 1
    For $b To $i_Abs Step 1
        For $a To $i_Abs Step 1
            If $a * $b == $i_num Then
                Return 0
            EndIf
        Next
    Next
    Return 1
EndFuncoÝ÷ ØGb´·¶­j«¨´Ú-ªê-Ø­Øêæk&Þ¶¬jëh×6Func _IsPrime($i_num)
    If Not IsInt($i_num) Then Return 0
    Local $Abs
    $Abs = Abs($i_num)
    If IsInt($Abs) Then
        Return 0
    EndIf
    Local $b = 0
    Local $a = 0
    For $b = 0 To $i_Num Step 1
        For $a = 2 To $i_Num Step 1
            If $a * $b == $i_num Then
                Return 0
            EndIf
        Next
    Next
    Return 1
EndFunc

Edited December 13, 2006 by darkshadow791

[AngelSL]

Made a GUI for it and improved the function.

If number is less than 2, return -2. And some I cannot remember

expandcollapse popup

#include <GUIConstants.au3>
#region IsPrime_Function
;===============================================================================
;
; Function Name:   _IsPrime
; Description:: Check if a number is prime or not
; Parameter(s): $i_num - Number to check
; Requirement(s):  None
; Return Value(s): 1 - Number is prime
;              0 - Number is not prime
;               -1 - String isn't a number
; Author(s):       RazerM
;
;===============================================================================
;
Func _IsPrime($i_num)
    If StringIsDigit($i_num) = 0 Then Return -1
    If $i_num > 3 Then
        If Mod($i_num, 2) = 0 Then Return 0
        If Mod($i_num, 3) = 0 Then Return 0
    EndIf
    If $i_num = 1 Then Return 1
    If $i_num <2 Then Return -2
    Dim $divisor, $increment, $maxdivisor
    $divisor = 5
    $increment = 2
    $maxdivisor = Sqrt($i_num) + 1

    Do
        If Mod($i_num, $divisor) = 0 And $i_num <> $divisor Then Return 0
        $divisor = $divisor + $increment
        $increment = 6 - $increment
    Until $divisor > $maxdivisor
    Return 1
EndFunc   ;==>_IsPrime




$Form1 = GUICreate("Prime Number Checker", 208, 100, 193, 115)
$number = GUICtrlCreateInput("", 8, 32, 193, 21)
$check = GUICtrlCreateButton("Check", 8, 64, 193, 25, 0)
$Label1 = GUICtrlCreateLabel("Number to check if it is a Prime Number:", 8, 8, 193, 17)
GUISetState(@SW_SHOW)

While 1
    $read = GUICtrlRead($number)
    $nMsg = GUIGetMsg()
    $isPrime = $read & " is a prime number."
    $notPrime = $read & " is not a prime number."
    $notNumber = $read & " is not a number, or is negative."
    $Negative = $read & " is zero or one."
    Switch $nMsg
        Case $GUI_EVENT_CLOSE
            Exit
    EndSwitch
    If $nMsg = $check Then
        $check2 = _IsPrime($read)
#cs     If $read = 1 Then
            GUISetState(@SW_HIDE)
            MsgBox(64, "Prime Number Checker", $isPrime)
            GUISetState(@SW_SHOW)
#ce     EndIf
        If $check2 = -1 Then ;& $read = NOT 1 Then
            GUISetState(@SW_HIDE)
            MsgBox(64, "Prime Number Checker", $notNumber)
            GUISetState(@SW_SHOW)
        EndIf
        If $check2 = 1 Then ;& $read = NOT 1 Then
            GUISetState(@SW_HIDE)
            MsgBox(64, "Prime Number Checker", $isPrime)
            GUISetState(@SW_SHOW)
        EndIf
        If $check2 = 0 Then ;& $read = NOT 1 Then
            GUISetState(@SW_HIDE)
            MsgBox(64, "Prime Number Checker", $notPrime)
            GUISetState(@SW_SHOW)
        EndIf
        If $check2 = -2 Then 
            GUISetState(@SW_HIDE)
            MsgBox(64, "Prime Number Checker", $Negative)
            GUISetState(@SW_SHOW)
        EndIf
    EndIf
WEnd

Edited June 4, 2007 by AngelSL

[RazerM]

I understand your new to the forums, but this is a User Defined Function (UDF) not a script ready to test for prime numbers. The return -2 isn't needed.

[Nutster]

There are several optimizations I can see regarding these methods.

• For - Next is faster than other loops.
• You only need to investigate up to the square root of the number you are interested in to determine prime-ness.
• Prime numbers are only interested in positive integers. Negative number are automatically considered composite, because you have to multiply by -1.

So: Untested, but should work out of the box.

Func IsPrime(Const $nValue)
    Local $nCheck

    If Not IsInt($nValue) Then
        ; Only valid for integers
        Return False
    ElseIf $nValue < 2 Then
        ; Negative numbers are composite.  0 and 1 are neither prime nor composite.
        Return False
    Else
        ; Could be good.
        For $nCheck = 2 to Int(Sqrt($nValue))
            If Round(Mod($nValue, $nCheck)) = 0 Then
                ; Round is needed because sometimes Mod returns a number really close to 0, but not exactly it.
                ; If $nCheck can divide $nValue, then it is composite
                Return False
            EndIf
        Next
        ; Did not trip anything else, so consider it prime.
        Return True
    EndIf
EndFunc

[Nutster]

I looked at the other scripts and saw one of the optimizations was to check for divisibility by 2 and then start skipping all the even numbers. This works because all the prime numbers are odd, except for 2. When I tried expanding the idea to 3 as well, I could not get it to work consistently on paper. So the new code would be:

Func IsPrime(Const $nValue)
    Local $nCheck

    If Not IsInt($nValue) Then
        ; Only valid for integers
        Return False
    ElseIf $nValue < 2 Then
        ; Negative numbers are composite.  0 and 1 are neither prime nor composite.
        Return False
    ElseIf Round(Mod($nValue, 2)) = 0 Then   ; Round is needed because sometimes Mod returns a number really close to 0, but not exactly it.
        ; Even number.  Not prime.
        Return False
    Else
        ; Odd number.  Could be prime.
        For $nCheck = 3 to Int(Sqrt($nValue)) Step 2
            If Round(Mod($nValue, $nCheck)) = 0 Then
                ; If $nCheck can divide $nValue, then it is composite
                Return False
            EndIf
        Next
        ; Did not trip anything else, so consider it prime.
        Return True
    EndIf
EndFunc

This version should be about twice as fast to identify a prime or composite as my previous version.

[pixartist]

what about this ?

Func isPrim($at, $n)
    Select
        case $n==2
            return "2 is a prime" 
        case $n<2
            return $n & " is not a prime"
        case $at*$at > $n
            return $n & " is a prime"
        case $n-(floor($n/$at)*$at)==0
            return $n & " is not a prime, it can be divided by " & $at
        case Else
            return isPrim($at+2, $n)
    EndSelect
EndFunc


MsgBox(0,"result", isPrim(2,InputBox("Prime?", "Enter a Number", "")))

[olivarra1]

i've made this

it shows you all the prime numbers that exist (if you put maximum: 1000, it computes the first 1000 prime numbers)

expandcollapse popup

#include <GUIConstants.au3>
#include <math.au3>
#Region ### START Koda GUI section ### Form=
$Form1 = GUICreate("prime numbers", 252, 212, 193, 125)
$ed_1 = GUICtrlCreateEdit("", 0, 0, 249, 185)
$bt_comencar = GUICtrlCreateButton("start", 0, 184, 123, 25, 0)
$qt_maxim = GUICtrlCreateInput("Maximum", 123, 185, 130, 25, 0)
GUISetState(@SW_SHOW)
#EndRegion ### END Koda GUI section ###
dim $num = 1, $contador = 0

While 1
    $nMsg = GUIGetMsg()
    Switch $nMsg
        Case $GUI_EVENT_CLOSE
            Exit
        Case $bt_comencar
            If GUICtrlRead($qt_maxim) > 0 Then
                $maxim = GUICtrlRead($qt_maxim)
                dim $primo[$maxim + 1]
                GUICtrlSetData($ed_1, 1 & @CRLF)
                while 1
                    if $contador = 0 Then
                        TrayTip("error", "there's no prime number", 5, 1)
                    Else
                        TrayTip("Computing", "actual number: " & $num & ". numbers found: " & $contador - 1 & ". Last computed number: " & $primo[$contador - 1], 5, 1)
                    EndIf
                    if $contador = $maxim then ExitLoop
                    $num = $num + 1
                    if $num < 4 Then
                        GUICtrlSetData($ed_1, GUICtrlRead($ed_1) & $num & @CRLF)
                        $primo[$contador] = $num
                        $contador = $contador + 1
                    Else
                        $a = 0
                        for $i = 0 to ($contador - 1)
                            if _MathCheckDiv($num, $primo[$i]) = 2 Then
                    ;MsgBox(0, "", $num & " " & $primo[$i])
                                $a = $a + 1
                            EndIf
                        Next
                        if $a = 0 Then
                            $primo[$contador] = $num
                            GUICtrlSetData($ed_1, GUICtrlRead($ed_1) & $num & @CRLF)
                            $contador = $contador + 1
                        EndIf
                    EndIf
                WEnd
                TrayTip("Prime", "Finished!", 5, 1)
            EndIf
    EndSwitch
WEnd

My english is not so well but...

olivarra1

PD: i want to post on example scripts, i have a lot of them ^^

Edited January 2, 2008 by olivarra1