5
\$\begingroup\$

I've come up with a very efficient way of finding if a number is prime, using TI-BASIC for use with TI-83/84/+/SE calculators. I am trying to optimize it however possible.

:Input "NUMBER: ",A
:If A<2 or fPart(A
:Then
:Disp "INVALID INPUT"
:Stop
:End
:0→B
:2→I
:While I<A and not(B
:If 0=fPart(A/I
:1→B
:I+2→I
:If I=4
:3→I
:End
:If B
:Disp "NOT"
:Disp "PRIME"

A few notes:

  • Lines 2-6 are for validating input, and don't affect the effectiveness of the program.
  • The closing "s on line 4 and the last two lines are not necessary, but I added them so the syntax would highlight nicely here.
  • Lines 12-14 are for speeding up the loop doubly; instead of incrementing by 1 each time, it is by 2, with the If to offset the 4 to 3 on the first run.
  • The not(B was very efficient, to end the loop whenever a match to identify the number as a composite number is found.
\$\endgroup\$
5
\$\begingroup\$

I do not speak TI-BASIC, so I cannot review the style, coding conventions etc. But there are two possible optimizations:

  • If a number A is composite then it must have a factor that is less than or equal to sqrt(A). So you can replace

    :While I<A and not(B
    

    with (and I am just guessing the syntax):

    :sqrt(A) -> S
    :While I<=S and not(B
    

    This reduces the number of trial divisions substantially if the input is a prime number.

  • Check the divisibility by 2 first, and then loop just over the odd numbers I = 3, 5, 7, .... This saves you from checking

    :If I=4
    :3->I
    

    in each loop iteration.

\$\endgroup\$
  • \$\begingroup\$ I can't really change my code here now that it's posted, but I had :While I²<A and not(B but the square didn't copy over for some reason... and thanks for the second suggestion. \$\endgroup\$ – Timtech Oct 23 '14 at 18:23
  • \$\begingroup\$ @Timtech: OK, but computing the square root once instead of I^2 in each iteration is usually faster. But I don't know if that applies to your calculator. \$\endgroup\$ – Martin R Oct 23 '14 at 18:27
  • \$\begingroup\$ Oh, that's right. I was just thinking in terms of looping up till I. Thanks! \$\endgroup\$ – Timtech Oct 23 '14 at 18:47
  • \$\begingroup\$ Wait, no! I is updated every time; of course you need to re-calculate it. \$\endgroup\$ – Timtech Oct 23 '14 at 19:02
  • \$\begingroup\$ @Timtech: My suggestion was to calculate S = sqrt(A) once, so that you don't have to calculate I^2 in each iteration. While I^2 < A is replaced by While I <= S. \$\endgroup\$ – Martin R Oct 23 '14 at 19:11

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.