Code: Select all

`t1 = timer`

do while primeList(most) = 0

Prime=TRUE

num += 2

for x = 1 to cMaxIndx

if (num mod primeList(x)=0) then

Prime=FALSE

exit for

end if

next x

if Prime then

cMaxIndx += 1

primeList(cMaxIndx)=num

end if

loop

t2=timer

ran faster then this code:

Code: Select all

` t1 = timer`

do while primeList(most) = 0

Prime=TRUE

num += 2

r = (num \ 2)+1

for x = 1 to cMaxIndx

if (num mod primeList(x)=0) and x < r then

Prime=FALSE

exit for

end if

next x

if Prime then

cMaxIndx += 1

primeList(cMaxIndx)=num

end if

loop

t2=timer

It actually ran MUCH faster. Finding the first 100000 prime numbers using method 1 took ~85 seconds while the second took ~170 seconds, shortcutting even futher by only going up to the sqroot of num (instead of half of num) took even LONGER... ~180 seconds. The less number of loops i tried to do the longer the program took!

I figure it must be something about checking two conditions per loop is slower then checking one condition many more times... but

A) Won't this eventually flip as the growth of checks increases, how to tell when this flip will occur?

and B) How to optimize further? Obviously adding a third check to see if that point has been reached will not help as that will only slow it down even more before that threshold is reached AND that threshold would increase.

I am going to try to test a few more things.... such as figuring out exactly how many more times the loop is being done for each method and stuff.

The code in its entierty is here:

Code: Select all

`cls`

Const FALSE = 0

const TRUE = not FALSE

const MOST = 100000

dim primeList(1 to most) as integer

dim as integer num,cMaxIndx,x,r

dim as integer Prime

dim as string k

dim as double t1,t2

num = 1

cMaxIndx = 1

primeList(1)=2

print "ready to go"

print "-----------"

sleep

t1 = timer

do while primeList(most) = 0

'k = inkey$

'if k = "q" then exit do

Prime=TRUE

num += 2

'r = (num \ 2)+1

for x = 1 to cMaxIndx

if (num mod primeList(x)=0) then ' and x < r then

Prime=FALSE

exit for

end if

next x

if Prime then

cMaxIndx += 1

primeList(cMaxIndx)=num

'? num; " is prime."

end if

loop

t2=timer

print "done"

print "found ";cMaxIndx;" prime numbers."

print "Time: ";t2-t1;" seconds.

print "The 1000th prime is: ";primeList(1000)

dim as integer f

f=freefile

open "d:\dev\freebasic\fbedit\myprojects\primes\pList.txt" for output as #f

for x=1 to most

print #f, primeList(x)

next x

print #f, t2-t1

close #f

sleep