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