I added just one line to your code Robert, because part of the rules are that on has to report the number of prime numbers as well. But it still runs in the same time. So, this is currently the best code:

#pragma BackgroundTasks False
#pragma BoundsChecking False
#pragma DisableBoundsChecking
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
dim n(-1) As Boolean
dim m As Integer = 1000000
redim n(m)
dim i,j,k As Integer
dim sum As int64 = 0
Dim startTime As Double
Dim endTime As Double
Dim count As Integer
startTime = Microseconds()
j = 2
while j<m
for k = j to m
if not n(k) then
sum=sum+k
count = count + 1
exit
end if
j=k
next
for i = k to m step k
n(i)=true
next
wend
endTime = Microseconds()
msgbox "Items: " + Str(count)
msgbox "Sum: " + Str(sum)
msgbox "Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"

Any more ideas how this can be improved even further?

I have an idea for an optimization that requires an acknowledgement that 2 is prime and no other even number is prime. Is that permitted under the rules?

Threading won’t help and would actually slow it down. On the other hand, here are my results:

Original:
Items: 78,498
Sum: 37,550,402,023
Time: 0.016 s
Mine:
Items: 78,498
Sum: 37,550,402,023
Time: 0.007 s

And the code:

const kMax = 1000000
dim notPrime( kMax ) as boolean
dim lastOuterIndex as integer = Sqrt( kMax ) + 1
for outer as integer = 3 to lastOuterIndex step 2
dim firstInnerIndex as integer = outer * outer
dim stepper as integer = outer * 2
for inner as integer = firstInnerIndex to kMax step stepper
notPrime( inner ) = true
next
next
dim sum As int64 = 2
Dim count As Integer = 1
for i as integer = 3 to kMax step 2
if notPrime( i ) = false then
count = count + 1
sum = sum + i
end if
next

Essentially, it does what Robert’s does, but it precomputes the primes and skips the even numbers.

Edit: This is a desktop app compiled with 64-bt aggressive running on a MacBook Pro 2.9 GHz i7.

This gives further speed improvement.
Time: 0.0142204 seconds

#pragma BackgroundTasks False
#pragma BoundsChecking False
#pragma DisableBoundsChecking
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
dim et As Double=Microseconds
dim n(-1) As Boolean
dim m As Integer = 1000000
redim n(m)
dim i,j,k As int64
dim sum As int64 = 2
dim count As Int64=1
j = 3
while k<m
for k = j to m step 2
if not n(k) then
n(k)=true
sum=sum+k
count=count+1
exit
end if
next
j=k
for i = k*k to m step k
n(i)=true
next
wend
et=(Microseconds-et)/1e6
txtAreaOut.Text="Count: "+str(count) +" Sum: "+str(sum) +" Time: "+str(et)+" seconds"

const kMax = 1000000
dim notPrime( kMax ) as boolean
dim lastOuterIndex as integer = Sqrt( kMax ) + 1
for outer as integer = 3 to lastOuterIndex step 2
if notPrime( outer ) = false then
dim firstInnerIndex as integer = outer * outer
dim stepper as integer = outer * 2
for inner as integer = firstInnerIndex to kMax step stepper
notPrime( inner ) = true
next
end if
next
dim sum As int64 = 2
Dim count As Integer = 1
for i as integer = 3 to kMax step 2
if notPrime( i ) = false then
count = count + 1
sum = sum + i
end if
next

On my 32-bit console compiled version I now get 0.029 with Kem’s algorithm and 0.033s with Robert’s algorithm.

I really need to think about upgrading my Xojo license again, because I cannot unfortunately test the 64-bit aggresively compiled code on my current license.

However, this is seriously impressive.

This morning I started with a 7s result, which is now down to 0.029s (0.005 on 64-bit bit). That is Insane.

Now imagine all the software in the world was written with this optimization effort, where the industry would be at.

Robert, FYI, loop indexes are calculated each time through the loop so you’re better off pre-calculating them. So:

for i = k*k to m step k

would be faster as:

dim firstK as Int64 = k * k
for i = firstK to m step k

Also, by using k as the step, you are flagging all the even numbers that you’re skipping anyway. For example, where k = 3, you flag 3, 6, 9, 12. Use k * 2 to skip the even numbers, but again, cached for speed.