However, the nostalgia came back, along with a better understanding of primes, and factors in general.
Under the spoiler is a description (the best I can word it) of the TI-basic environment. If you already know about it, skip ahead.
If I remember correctly, you can only hold around 2300 elements in memory (each integerish value acts as an element, whether it's by itself, in an array, or otherwise.) however I may be slightly off on that number.
The processor is slow as a turtle, so even saving something as simple as a subtraction will make it noticably faster.
Here's psuedocode (runnable in python, but still not Ti-Basic, so the label 'psuedo' still applies) for what I wanted to do.
Code: Select all
n = 1009 * 2 #number to be factored
m = n #for the sake of not destroying the original
sieve = ['1']*1000 #don't use 0!
sieve = 0 #for the hell of it
sieve = 0 #ti fo lleh eht rof
pfacs =  #prime factors
exitcode = 1 #0 is ok, 1 is too big a prime
for i in range(2,1000):
#Look ma! it's prime!
#Does it kill the number?
while (m % i == 0):
m /= i
if (m == 1):
exitcode = 0
break #I'm gonna get attacked by a raptor when I do this in TI-Basic
#nope, keep going!
j = 2
while (i*j < 1000):
#kill all the multiples!
sieve[i*j] = 0
j += 1
#yay! error handling!
if exitcode == 1:
print "Prime factor > 999 in number."
print "Unresolved factor:",m
print "Prime factors found:"
Now, my question is:
can somebody suggest ways to get more than the primes < 1000, relatively progressively? (That way I can do the checking, and only find the biggest prime that I need to)
I had two thoughts. The first one was to backpedal slightly, and figure out each prime by doing a loop and testing it against all the previous primes. This would allow me to find the first 999 primes (as opposed to the primes < 999), however it would use more cycles and get rid of the elegance of erasthones' sieve. (And actually, I implemented this idea before as a simple prime-generator. I think I only found the first 500 or so before it ran out of memory, and even that took ages.)
The other idea was to save the primes in a second list. When I exhaust the first list (find all the primes < 999) clear it and then find all the primes from 1000 - 1998 (I'd have to iterate over the old list of primes to re-scratch out their multiples, but if you've got a prime > 1000, it's gonna take some serious cycles anyway.) In effect, paging out the sieve as I use it up.
I haven't managed to dig my old TI up out of whatever box it's hiding in, so I can't test the effectiveness of this algorithm yet (plus I'm describing the TI environment out of memory), but it feels promising. Plus, instant prime factors of 2002! (2002 factorial) was quite impressive. (Albeit, it was in python, but still.)
Here's a one-liner for factorial if you feel like feeding the program gawdawful numbers. (when I was testing it, I meant to type 2002, not fact(2002), but hey. I'm still being impressed over that.)
Code: Select all
def fact(x): return reduce(lambda x, y: x*y, xrange(2, x+1))
Suggestions? Comments? Kudos? Cookies?