Mega Simple Optimization Questions

[mezz]

I created a simple little program to find prime numbers today.
This is one of my first TI BASIC programs, but I have read a bit about optimization and how to code well on it. I don't have any other coding experience though =/



0->B \\prepare B, used to count number of primes found
2->LPR(1 \\Make sure 2 and 3 are given primes on custom list "L PR"
3->LPR(2

Input "FIND N PRIMES: ",N \\User Inputs number of primes to find and append to list LPR

startTmr->θ \\For timing the different programs. the variable is theta

Lbl A \\Program will look back to here until N primes are found

dim(LPR->D \\number of primes in the list. The list isn't cleared every time so it can add up for later

2+LPR(D->X \\Starting value X is highest known prime + 2 (evens aren't prime)

1->A \\Prep A, used to go up and down the primes list to check for divisibility

Repeat LPR(A)>=(.5LPR(D \\repeats until all the primes up to half the number have been tried. Higher than 1/2 of X and they surely can't divide.

If not(fPart(X/LPR(A \\Checks to see if X is evenly divisible by a known prime. If it is divisible X is incremented by 2 and we start dividing by 3 again.
Then
2+X->X \\not going to deal with evens at all...
1->A \\A will be 2 by the time it tries again
End
A+1->A \\Goes to the next known prime to use as a divisor
End \\repeat ends if all known primes up to 1/2 of X have been tried, so X must be prime

X->LPR(D+1 \\stores a new prime to the end of the primes list

Disp X \\So you can see them whiz by , optional

1+B->B \\increments so we can stop it at the desired number of primes

If B!=N
Goto A \\loops everything

checkTmr(θ->L1(1 \\outputs my time




Starting with a blank LPR list:

Without the "disp X" my time is 23 seconds! (for the first 50 primes. setting N to 48, it starts with 2 and 3)
With disp x my time is 26 seconds

I checked this with a known primes list and it works. I am just wondering if I can optimize it more without learning ASM. So far this is the fastest one I've used, and I downloaded a couple so I'm pretty happy

[Harrierfalcon]

First, you can replace the goto loop with "Repeat B=N". Save a few bytes and time.
Rather than using LPR, use something like L1 or L2, the system lists.

Welcome to UnitedTI!

[mezz]

Ah thanks, the repeat should help
Are the system lists any different? I have plenty of memory and was worried because I have to use my regular system lists sometimes.
I guess it would save bytes in the program though.. hmm. I'll use L6.

Thanks !'

Still it's at a healthy 23 seconds. This is kicking the pants off of any of the ones I downloaded and tested the time for.

It should matter a lot more for longer runs of say... N= 997 heh

[luby]

0->b can be delvar b
2->LPR(1
3->LPR(2
can be {2,3->pr(1 // don't need the L

those I see right off the bat.

[Weregoose]

[mezz]

I can see the DelVar, but there may be a problem with "{2,3->L6"
I don't want the whole list to be overwritten, so I can continue it later.

Changed to :
DelVar B2->L6(1
3->L6(2

Changed to: Repeat L6(A)>Sqrt(X

I was trying that before, but I had >= and didn't notice so 9 was "prime" and it messed the whole thing up. With just > it works really, really fast.


13 seconds!!!!!!!

Thanks guys!

EDIT: 11 seconds without Disp X. Jeez! What a difference

Here's the most current version. I decided to use a For( loop because I was incrementing B anyway.
Also, I stored Sqrt(X to Y to save computation

[thornahawk]

Reminds me... here's a prime number sieve I wrote a while back, returning all primes less than or same as N: