Jump to content
Sign in to follow this  
erifash

small _prime function

Recommended Posts

Here is the smallest of the functions that check if a number is prime or not:

Func _prime($num)
  If $num < 2 or $num <> Int($num) Then Return -1
  For $i = $num To 2 Step -1
    If $i <> $num Then
      If $num / $i = Int($num / $i) Then Return 0
    EndIf
  Next
  Return 1
EndFunc

Returns 1 if it is prime or 0 if it's not or -1 if there is an error.

Unfortunately, the bigger the number is, the longer it will take...

Share this post


Link to post
Share on other sites

I see three things...

First, don't return -1 on error, set the @error macro. The reason is, a function like this is best used as:

If _prime($num) Then ...

The problem is, -1 is true. Only 0 is false in AutoIt. Thus, this will return "true" when you mean to return an error state.

Second, instead of:

$num <> Int($num)

You can use:

IsInt($num)

Lastly, and possibly a performance improvement...

Isn't:

If $num / $i = Int($num / $i) Then Return 0

The same as:

If Not Mod($num, $i) Then Return 0

Thats one less divide, and divide is a very expensive operation.

Edit: Fixed mistake in code (Hopefully).

Edited by Valik

Share this post


Link to post
Share on other sites

Thanks guys. Is this the code you mean?

Func _prime($num)
  If $num < 2 or not IsInt($num) Then Return 0
  For $i = $num To 2 Step -1
    If $i <> $num Then
      If not Mod($num, $i) Then Return 0
    EndIf
  Next
  Return 1
EndFunc

Edit: Fixed a small bug in the code.

Edited by erifash

Share this post


Link to post
Share on other sites

I think it is better from 3 to the number. Many number can be divided by small numbers, like 3, 5, 7, 11...

MsgBox(0, '', _prime(4999))

Func _prime($num)
   If $num < 2 Or Not IsInt($num) Then Return 0
   If Not Mod($num, 2) Then Return 0
   For $i = 3 To Int(Sqrt($num) + 1) Step 2
      If $i <> $num Then
         If Not Mod($num, $i) Then Return 0
      EndIf
   Next
   
   Return 1
EndFunc  ;==>_prime

Share this post


Link to post
Share on other sites

in fact, try this:

$t = TimerInit()
For $c = 1 to 1000
   _prime1($c)
Next
MsgBox(0,'','erifash ms ' & TimerDiff($t))

$t = TimerInit()
For $c = 1 to 1000
   _prime2($c)
Next
MsgBox(0,'','ezzetabi ms ' & TimerDiff($t))

Func _prime1($num);erifash
  If $num < 2 or not IsInt($num) Then Return 0
  For $i = $num To 2 Step -1
    If $i <> $num Then
      If not Mod($num, $i) Then Return 0
    EndIf
  Next
  Return 1
EndFunc

Func _prime2($num);ezzetabi
   If $num < 2 Or Not IsInt($num) Then Return 0
   If Not Mod($num, 2) Then Return 0
   For $i = 3 To Int(Sqrt($num) + 1) Step 2
      If $i <> $num Then
         If Not Mod($num, $i) Then Return 0
      EndIf
   Next
   
   Return 1
EndFunc;==>_prime
Edited by ezzetabi

Share this post


Link to post
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
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...