Factoring a number

Here's my program for factoring a number. It works, but it's quite slow.

I'm looking for suggestions for optimizing. The lines are indented just for readability.

ClrHome
Disp "N=Number
Input "N: ",N
If N≥1 and not(fPart(N:Then
    {1→ʟF
    If N≥2:Then
        For(A,2,iPart(√(N)))
            If not(fPart(N/A
                A→ʟF(1+dim(ʟF
        End
        dim(ʟF)-(0=fPart(√(N→B
        For (A,B,1,‐1
            N/ʟF(A→ʟF(1+dim(ʟF
        End
    End
End
If N≥1 and not(fPart(N
    ʟF

The vast majority of your time, especially with larger numbers, is spent in the inner loop:

For(A,2,iPart(√(N)))
If not(fPart(N/A
    A→ʟF(1+dim(ʟF
End

There are three ways you can speed this up.

Use the built-in remainder( command

If you have a TI-84+ series calculator with a MathPrint or color OS, you can use not(remainder(N,A rather than not(fPart(N/A, which will give you ~20% faster code.

Don't check numbers you don't have to

You can do this in two ways: first, recalculate the limit of division so that division doesn't go up to sqrt(N) every time, and second, skip numbers that you already know cannot divide N. For example, once you know N is odd, you don't need to divide it by any even numbers. Note that if you do this, you will be finding the prime factors of a number, not all factors, which may not be what you want.

Divide by whole lists of numbers

TI-BASIC is a very slow language. There is no compiler to optimize for you, and the interpreter is slow and much less sophisticated than the ones in today's languages. It is therefore important in TI-BASIC to write code with the limitations of the calculator in mind. The interpreter will not need to jump back and forth in the For loop every time if you divide by a whole list of numbers at once. To combine this with the sieving idea, you can set a list to {7,11,13,17,19,23,29,31}; that is, all numbers relatively prime to 2, 3, and 5, and add 30=235 to your index every time through the For loop, saving the interpreter time.

I use these optimizations in a prime factorization routine I wrote, except that I use numbers relatively prime to 210 rather than 30:

/* L1 holds the factors
 * L2 is the list of numbers relatively prime to 210.
 * A is a possible divisor
 * B is the index for batch dividing
 * C saves B so the Goto trick can be used.
 * X is the number to be factored
 */

ClrHome
Prompt X
startTmr→T
DelVar CClrList L₁
cumSum({11,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,\
    6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2→L₂ //numbers relatively prime to 210

For(A,2,13 
Lbl 1
While not(remainder(X,A //Check for small factors that occur more than once
X/A→X
A→L₁(1+dim(L₁
Output(8,1,A
End
End //exits first For loop, but also the second one when jumping back

//Main loop for batch dividing
For(B,C,sqrt(X),210)
If min(remainder(X,B+L₂
End

L₂+B
min(Ans+E9remainder(X,Ans→A //Smallest divisor if it exists; very large num if not
B→C
X→B      //Now B>>sqrt(X), so at the next End the For( loop will finally end.
If A²≤X
Goto 1  //goes back to divide X by A

If X>1
X→L₁(1+dim(L₁
Disp "TIME:", checkTmr(T
Disp dim(L₁
Pause L₁

This can factor the number 19991 * 49991 = 999370081 in less than 24 seconds (it takes at least 200 the simple way), and check that 8675309 is prime in five seconds on a TI-84+.

StackExchange Code Review Q#84101, answer score: 5