_isprime Function

[RazerM]

I made a function to see if a number is prime or not. I was bored This has been updated and the function below does work

;===============================================================================
;
; 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 0
    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

Edit: updated to most recent code

Edited May 19, 2006 by RazerM

[VicTT]

There is an infinity of factors to be checked before concluding that a number is prime or not(This can be proven)...Your script is incomplete and thus, useless for any prime number higher or equal to 23...Post_Number++;

[Wus]

I fail to see how this function would work.

You are trying to test for primeness based on a finite set of primes. But seeing as how there are infinite primes that wont work. All I had to do to fool your algorithm was to take the next prime after 19 and square it.

ie:

your function tells me that (23*23) or 529 is prime when its obviously the product of two integers.

Prime tests usually have to test the majority of the values from from i=2 to i=int(sqrt(testVal)) +1 for divisability.

This can be seen here http://www.devx.com/vb2themax/Tip/19051

[RazerM]

thanks for the feedback guys. Based on that site Wus i made this

;===============================================================================
;
; Function Name:   _IsPrime
; Description:: Check if a number is prime or not
; Parameter(s): $i_num - Number to check
; Requirement(s):  Math.au3
; Return Value(s): 1 - Number is prime
;                  0 - Number is not prime
; Author(s):       RazerM
;
;===============================================================================
;
Func _IsPrime($i_num)
    If $i_num > 3 Then
        If Mod($i_num, 2) = 0 Then Return 0
        If Mod($i_num, 3) = 0 Then Return 0
    EndIf
    Dim $divisor, $increment, $maxdivisor
    $divisor = 5
    $increment = 2
    $maxdivisor = Sqrt($i_num) + 1

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

It appears to work but it returns 0 when i test 5 and 5 is definetely prime

[Daniel W.]

Maybe because your Divisor is 5?

I dont know because for me your code is very difficult to understand ( i am newbie atm )

[RazerM]

Thanks, thats it!

;===============================================================================
;
; 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
; Author(s):       RazerM
;
;===============================================================================
;
Func _IsPrime($i_num)
    If $i_num > 3 Then
        If Mod($i_num, 2) = 0 Then Return 0
        If Mod($i_num, 3) = 0 Then Return 0
    EndIf
    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

I removed the Math.au3 in requirement and made sure it checked whether the number and the divisor were the same or not before returning 0

[RazerM]

if you use ConsoleWrite on $increment you will see it alternates between 2 and 4 like it is meant to.

I have updated mine to return 0 if the number is 1

;===============================================================================
;
; 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
; Author(s):       RazerM
;
;===============================================================================
;
Func _IsPrime($i_num)
    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 0
    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 - Abs($increment)
    Until $divisor > $maxdivisor
    Return 1
EndFunc  ;==>_IsPrime

Edited April 13, 2006 by RazerM

[Daniel W.]

$zahl = InputBox("Zahl angeben", "Geben Sie an welche Zahl zu überprüfen ist.")
            If $zahl = 3 Then
            MsgBox(0, "", "Primzahl")
            ElseIf $zahl = 5 Then
            MsgBox(0, "", "Primzahl")
            ElseIf $zahl = 7 Then
            MsgBox(0, "", "Primzahl")
            ElseIf $zahl = 529 Then
            MsgBox(0,"", "Keine Primzahl")
            Else
            $I_Result = _MathCheckDiv($zahl, 2)
            If $I_Result = 2 Then
               MsgBox(0,'','Keine Primzahl')
            Else
               $I_Result = _MathCheckDiv($zahl, 3)
               If $I_Result = 2 Then
            Msgbox(0, "", "Keine Primzahl")
               Else
               $I_Result = _MathCheckDiv($zahl, 5)
               If $I_Result = 2 Then
            Msgbox(0, "", "Keine Primzahl")
               Else
            $I_Result = _MathCheckDiv($zahl, 7)
               If $I_Result = 2 Then
            Msgbox(0, "", "Keine Primzahl")
            Else
            Msgbox(0, "", "Primzahl")
            EndIf
            EndIf
            EndIf
            EndIf
            EndIf

Hmm kk razerM and Wus

I am newbie atm so thats just the beginning of my autoIT programms maybe i get better later

Msgboxes are in German cuz i am from Germany dont wonder so ^^

Edited April 13, 2006 by Daniel W.

[RazerM]

it doesnt work, Daniel W. You need to consider a lot more factors. try and understand what is in my script or Larry's

[Wus]

Mine should be working completly, if you find an error in it. Tell me

Msgboxes are in German cuz i am from Germany dont wonder so ^^

The problem is that your testing your input against a finite set of known primes, this cannot work since there are infinite primes. You cant use that apporach.

[Confuzzled]

You code works, but the algorithm is flawed.

[RazerM]

You code works, but the algorithm is flawed.

My code or Daniels code?

[greenmachine]

Mine is more along the lines of Larry's, but it does fewer because it only goes to the sqrt of the inputted number instead of half (sqrt is the correct middle). It returns an array with the prime status at [0], the first divisor at [1], and the result of the division at [2].

$prime = _checkforprime (236993)
If Not @error Then
    _ArrayDisplay ($prime, "prime")
EndIf

Func _checkforprime($numcheck)
    Local $divisor[3]
    If Not IsInt ($numcheck) Then
        SetError (1)
        Return -1
    EndIf
    If Mod ($numcheck, 2) = 0 Then
        $divisor[0] = 0
        $divisor[1] = 2
        $divisor[2] = $numcheck/2
        Return $divisor
    EndIf
    For $i = 3 To Int (Sqrt ($numcheck)) + 1 Step 2
        If Mod ($numcheck, $i) = 0 Then
            $divisor[0] = 0
            $divisor[1] = $i
            $divisor[2] = $numcheck/$i
            Return $divisor
        EndIf
    Next
    $divisor[0] = 1
    $divisor[1] = 1
    $divisor[2] = $numcheck
    Return $divisor
EndFunc

[RazerM]

ive added another check to mine

;===============================================================================
;
; 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 0
    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

Edited April 21, 2006 by RazerM

[GrungeRocker]

why do you need to check if a number is a prime?

EDIT1:

well i search for an old cpp example of this

EDIT2:

ok its not the same, but here you are (its in c++)

expandcollapse popup

#include <iostream>

using namespace std;

int main(){
int anfang, ende;
int anzprim = 0;

cout<<"Calc Primenumbers from:";
cin>>anfang;

cout<<"to:";
cin>>ende;

if (anfang < 2)
anfang = 2;

for (int zahl = anfang; zahl <= ende; ++zahl){
int anzteiler = 0;
int teiler = 2

while((anzteiler == 0 ) && (teiler < zahl)){
if (zahl % teiler == 0)//zahl is not a prime
anzteiler++;

teiler++;
}

if (anzteiler == 0){//zahl is a prime
cout<<zahl<<"";
anzprim++;
}
}

cout<<endl<<anzprim<<" primenumbers were found."<<endl;

return 0;
}

Edited April 14, 2006 by GrungeRocker

[RazerM]

If you are referring to my script then it is only a function. You need to call it like this:

_IsPrime($n)

where $n can be any number

[jaenster]

;Teh thing by jaenster
func omfg($lol)
if $lol/2 = round($i/2) then
 return 1
endif
return 0
endfunc

[jvanegmond]

Here's a funny checker: I only translated Eratosthenes function from some language to AutoIt.

expandcollapse popup

$prime = Eratosthenes(50000)
For $x = 0 to UBound($prime)-1
    ToolTip("Now checking: " & $x & " prime: " & $prime[$x], 0, 0)
    If LarryPrime($x) <> $prime[$x] Then
        MsgBox(0, @ScriptName, "LarryPrime is flawed, at number: " & $x)
    EndIf
    If _IsPrime($x) <> $prime[$x] Then
        MsgBox(0, @ScriptName, "_IsPrime is flawed, at number: " & $x)
    EndIf
Next

Func Eratosthenes($n)
    Dim $a[$n+1]
    For $i = 0 to 1
        $a[$i] = 0
    Next
    For $i = 2 to $n
        $a[$i] = 1
    Next
    Dim $p = 2
    While $p^2 < $n+1
        $j = $p^2
        While $j < $n+1
            $a[$j] = 0
            $j = $j + $p
        WEnd
        Do
            $p += 1
        Until $a[$p] = 1
    WEnd
    Return $a
EndFunc

Func LarryPrime($number)
    Local $DaNum
    $DaNum = Abs($number)
    If $DaNum < 2 And $DaNum > -2 Then Return 1
    For $n = 2 to Int(($DaNum/2) + 1)
        If Mod($DaNum,$n) = 0 Then Return 0
    Next
    Return 1
EndFunc

Func _IsPrime($i_num)
    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 0
    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 - Abs($increment)
    Until $divisor > $maxdivisor
    Return 1
EndFunc  ;==>_IsPrime

Edit: If someone has the CPU power and time to run it up to 100000 please do! And tell me some of the results.

Edited September 18, 2006 by Manadar

[RazerM]

Using my _IsPrime function i calculated 224908 prime numbers. The file is 3.24mb

[Wus]

Edit:

I call myself good at math, but apparently I know absolutely nothing about number theory.

Edited September 19, 2006 by Wus