Little programming exercise

[Inverted 5]

Just wanted to waste some time and converted some php code to AutoIt :

$primeNumbers = array();
$output = '';
$start = microtime(TRUE);
for ($i = 2; $i < 100000; $i++)
{
     $divisible = false;
     foreach ($primeNumbers as $number)
     {
             if ($i % $number == 0)
             {
                     $divisible = true;
                     break;
             }
     }
     if ($divisible == false)
     {
             $primeNumbers[] = $i;
             $output .= $i;
     }
}
echo count($primeNumbers), "n";
echo "time: ", microtime(TRUE) - $start, "n";

#include <Array.au3>

Dim $primes[1]
Local $number
$output = ''

For $i = 2 To 100000
$divisible = false

For $number In $primes
If Mod($i, $number) = 0 Then
$divisible = true
ExitLoop
EndIf
Next

if $divisible = false Then
_ArrayAdd($primes, $i)
$output &= $i
EndIf
Next

MsgBox(0,'',UBound($primes))

Well, except the timing functions which I decided there's no reason to add after I ran it lol , would you say this code is equivalent ? It returns the same number of results (plus one, I guess it's the initialization I had to use ?) so I guess it runs fine.

EDIT: AutoIt code tag my ass ....

Edited October 22, 2012 by Inverted

[JohnOne 1,603]

I don't know much about maths, but I believe prime numbers can only be odd

so it makes no sense to test even numbers, also it will half the speed.

[jchd 1,506]

Well, except 2

[Inverted 5]

I guess setting step to 2 would be a good start, but what matters, is that the algorithm is as much the same as possible, for comparison's sake.

If I understanf correctly, constantly using ArrayAdd is the main performance hog, because it has to ReDim the array ? Or am I wrong ?

What is a more efficient alternative to the way I do the array operations ?

[Melba23 3,396]

Inverted,

What is a more efficient alternative to the way I do the array operations ?

Take a look at the last example in the Recursion tutorial in the Wiki and the text beneath it.

M23

[Spiff59 54]

I'd think preallocating your array, and then a single redim at the end would be the way to go:

#include <Array.au3>

Local $max = 1000, $primes[100 + $max * .17] = [2], $idx

For $i = 3 To $max Step 2
    For $j = 0 to $idx
        $rem = Mod($i, $primes[$j])
     If $rem = 0 Then ExitLoop
    Next
    If $rem Then
     $idx += 1
     $primes[$idx] = $i
    EndIf
Next
ReDim $primes[$idx + 1]
_ArrayDisplay($primes, $idx + 1 & " found")

edit: trying to tune the preallocated array size

Edited October 23, 2012 by Spiff59