Sieve of Eratosthenes for prime generation

Question

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've decided to also add some backstory to it.

In high school I would write inefficient programs that generated mathematically significant results, at least to me, and then have hours of fun optimizing and revising the code until it was as clean and fast as I could make it. While I was writing this sieve, I was exploring the generation of primes.

---

Currently, the code will generate a range of natural numbers from \$1\$ to \$N\$ and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as \$0\$ and storing each prime in a secondary list.

While this solution works just fine, one of the optimizations that I could never wrap my head around writing the code for was removing the multiples of primes instead of simply marking them as \$0\$.

The benefits of doing this are as follows:

• Faster execution
• Less memory usage
• No need for cleanup
• No if statements required

The problem is that I'm having a hard time wrapping my head around how I could perform this optimization and still remove multiples of each prime efficiently. If anyone has any ideas on how to do this in TI-Basic, please mention it.

What other optimizations could I make to the code as it is now?

Note: I do use an indentation system here because I loved the readability that indentation provides to languages like Python. Could this have any noticeable impact on the performance of the program?

:ClrList L2
:Input "END: ",E
:E->dim(L1:Fill(1,L1:cumSum(L1->L1
:For(A,2,E)
::If L1(A:Then
:::L1(A->L2(dim(L2)+1
:::For(B,2A,E,A
::::0->L1(B
:::End
::End
:End
:L2

Clarification:

E->dim(L1:Fill(1,L1:cumSum(L1->L1 generates the range from \$1\$ to \$N\$.

Answer 1

Removing a single number from a TI-BASIC list takes O(N) time where N is the size of the list. It's simply not practical. Here is the fastest idiom for removing the Xth element:

seq(L₁(A+(A≥X)),A,1,dim(L₁)-1→L₁

As for the indentation, the TI-BASIC interpreter needs to step through one colon at a time, which is relatively fast but not instantaneous. I expect each extra colon to take a TI-84 series calc about 0.1 ms each time through. If you want to maximize speed, get rid of the indentation.

As for other optimizations:

Rather than using E->dim(L1:Fill(1,L1:cumSum(L1->L1 to generate the list, use

cumSum(binomcdf(E-1,0→L₁

which has the same effect.

You can prescan for numbers not divisible by 2, etc; try this:

augment({2},1+2cumSum(binomcdf(int(.5E),0

to generate only the odd numbers.

As a different approach, you can generate prime numbers by adding to, not removing from, a list:

{2
For(𝑛,3,E,2)       ;close parenthesis to fix parser bug; step by 2 to catch odd numbers
If min(fPart(𝑛/L₁
n→L₁(1+dim(L₁
End
L₁

It should be of comparable speed or faster.

As a small tip, use the sequence variable n instead of a loop index. It takes as much as 0.5 milliseconds less to access (depending on how many other variables are in your VAT).