Omnimaga
Calculator Community => TI Calculators => TI-BASIC => Topic started by: Xeda112358 on May 13, 2013, 08:43:21 pm
-
So here is my palprime program, but after seeing Jim Bauwens' program and seeing that it could be tweaked to be much smaller and faster than mine, I don't know how much this is worth :P
Ans→N
0
If N<1 or fPart(N
Return
If N<6
Then
{2,3,5,7,11
Ans(N
Return
End
N-5→N
9→B
1→A
While N
B+1→B ;generate the next palindrome
If Ans=10A
Then
Ans→A
Else
If not(remainder(B,A
1+B+A(1+2(B=4A→B
End
B→C
.1Ans→D
While iPart(D
.1iPart(D→D
10(C+fPart(D→C
End ;palindrome is in C
If min(remainder(C,{3,7,11 ;Check primality
Then
√(C→D
{13,17,19,23,29,31,37,41
While max(Ans)≤D and min(remainder(C,Ans
Ans+30
End
N-not(not(min(remainder(C,Ans→N
End
End
CFor timings, I got 14 seconds for the 42nd prime palindrome, 58 seconds for the 100th, 494 seconds for the 290th.
Input is the 'nth' prime palindrome to return in Ans, and output is the nth prime palindrome (output in Ans).
-
What algorithm did you use to compute the primes?
-
Oh, it just uses a fairly simple trial division algorithm. I at one point uses a Fermat prime test modulo 2, but that algorithm is just too slow for anything smaller than 9 digits (in TI-BASIC it is, anyways). While it can return if a number is prime many times faster than trial division, it tends to be much slower than trial division at returning whether or not a number is composite (which is most numbers). So in the end, I found that it saved time to just remove the code for the Fermat test.
So instead, since all composite numbers except 2,3,5 are of the form 30k+{7,11,13,17,19,23,29,31}, I just check to see if any of those numbers are factors of the number up until the square root. The relevant code is:
If min(remainder(C,{3,7,11 ;Check primality
Then
√(C→D
{13,17,19,23,29,31,37,41
While max(Ans)≤D and min(remainder(C,Ans
Ans+30
End
N-not(not(min(remainder(C,Ans→N
End