2
\$\begingroup\$

I wrote a program to find all the prime numbers up to N on my TI-84, however, it is quite slow for any number above, like, 50. Are there any ways to optimize my code?

(I added comments using //)

Input N
{2}→L₂
For(I,3,N,2) // Loop through every odd number up to N starting at 3
1→J
0→H
√(I)→S
While L₂(J)≤S and H=0 // checks every previously found prime # less than sqrt(I)
If remainder(I,L₂(J))=0
1→H // used to break the loop

J+1→J
End
If H=0 // if no numbers divided evenly, add it to the list
augment(L₂, {I})→L₂     

End

Disp L₂ 

Thanks!

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

For factorization, the state of the art (as of like 1999, but also today as far as I know) is something like Rob Gaebler's ABIGSIV: https://www.ticalc.org/archives/files/fileinfo/79/7923.html

The essential idea is to use the "wheel" method. Make a list of all the prime numbers between 1 and 2*3*5*7 and stash that list in L1; then, do trial-division by L1+210*I all at once. The important thing is to maximize the amount of time you spend doing divisions and minimize the amount of time you spend doing bookkeeping.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You suggest a faster algorithm. Perhaps you can clarify how this is a review of the posted code. \$\endgroup\$
    – Martin R
    Apr 17, 2021 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.