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
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
E->dim(L1:Fill(1,L1:cumSum(L1->L1 generates the range from \$1\$ to \$N\$.