Jump to content

_isprime Function


RazerM
 Share

Recommended Posts

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 by RazerM
My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

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++;

Quote

Together we might liveDivided we must fall

 

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

Maybe because your Divisor is 5?

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

--------------------------------------------------------------------------------------------------------------------------------Scripts : _Encrypt UDF_UniquePCCode UDF MS like calculatorInstall programm *UPDATED* --------------------------------------------------------------------------------------------------------------------------------[quote name='Helge' post='213117' date='Jul 26 2006, 10:22 AM']Have you ever tried surfing the internet with a milk-carton ?This is similar to what you're trying to do.[/quote]

Link to comment
Share on other sites

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

My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

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 by RazerM
My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

$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 :think:

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

Edited by Daniel W.

--------------------------------------------------------------------------------------------------------------------------------Scripts : _Encrypt UDF_UniquePCCode UDF MS like calculatorInstall programm *UPDATED* --------------------------------------------------------------------------------------------------------------------------------[quote name='Helge' post='213117' date='Jul 26 2006, 10:22 AM']Have you ever tried surfing the internet with a milk-carton ?This is similar to what you're trying to do.[/quote]

Link to comment
Share on other sites

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

My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

Mine should :think: 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.

Link to comment
Share on other sites

You code works, but the algorithm is flawed.

My code or Daniels code?
My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

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
Link to comment
Share on other sites

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 by RazerM
My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

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

EDIT1:

well i search for an old cpp example of this :think:

EDIT2:

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

#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 by GrungeRocker

[font="Verdana"]In work:[list=1][*]InstallIt[*]New version of SpaceWar[/list] [/font]

Link to comment
Share on other sites

  • 5 months later...

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

My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

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

$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 by Manadar
Link to comment
Share on other sites

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

My Programs:AInstall - Create a standalone installer for your programUnit Converter - Converts Length, Area, Volume, Weight, Temperature and Pressure to different unitsBinary Clock - Hours, minutes and seconds have 10 columns each to display timeAutoIt Editor - Code Editor with Syntax Highlighting.Laserix Editor & Player - Create, Edit and Play Laserix LevelsLyric Syncer - Create and use Synchronised Lyrics.Connect 4 - 2 Player Connect 4 Game (Local or Online!, Formatted Chat!!)MD5, SHA-1, SHA-256, Tiger and Whirlpool Hash Finder - Dictionary and Brute Force FindCool Text Client - Create Rendered ImageMy UDF's:GUI Enhance - Enhance your GUIs visually.IDEA File Encryption - Encrypt and decrypt files easily! File Rename - Rename files easilyRC4 Text Encryption - Encrypt text using the RC4 AlgorithmPrime Number - Check if a number is primeString Remove - remove lots of strings at onceProgress Bar - made easySound UDF - Play, Pause, Resume, Seek and Stop.
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...