Prime Factorization – Actual Code

I finally had a little time free and put together a solution to the prime factorization problem. As with the tic-tac-toe program before, there are lots of opportunities to make this program better. This only runs once, rather than looping. The number being factored is a constant so you have to edit the program to get the factors of a different number. I limited the list of primes so the program as it stands will only compute the prime factors of numbers less than 65,535 (an homage to the old 8-bit days).Here’s the code:

10 REM We need a maximum number. Let's go ahead and say we'll hold an array
20 REM of all the primes up to 256. That lets us factorize all the integers
30 REM up to 65535, which was the largest int back in the days of 8 bit computers.
40 REM Since we're really only writing down the odd numbers, the array only
50 REM needs to be 128 cells wide.
60 DIM o(128)
70 REM compute our list of primes
80 PRINT "Computing prime numbers up to 257"
90 FOR i=1 to 128
100 o(i) = 1
110 NEXT i
120 REM Now we can start choosing primes and marking non-primes
130 FOR i=1 to 128
140 IF o(i) = 1 THEN
150 REM This number is prime!
160 let p = (i*2)+1
170 PRINT p
180 REM We need to mark all the multiples of p as not prime
190 FOR n=(i+p) to 128 STEP p
200 o(n) = 0
210 NEXT n
220 ENDIF
230 NEXT i
240 REM select a number to factorize
250 LET F = 5286
260 PRINT "Computing prime factors of ";F
270 REM compute the square root of the number. this is our fencepost
280 LET FP = SQRT(F)
290 REM 2 isn't in the array, but we need to check it anyway
300 LET i = 0
310 LET p = 2
320 REM while the current prime is less than or equal to the fencepost
330 if p  1 THEN
490 PRINT f;" - all done!"
491 GOTO 500
492 ENDIF
493 PRINT " - all done!"
500 END
510 REM get the next prime
520 i = i+1
530 if i > 128 THEN
540 p = FP + 1
550 RETURN
560 ENDIF
570 if o(i) = 1 THEN
580 p = (i * 2) + 1
590 RETURN
600 ENDIF
610 GOTO 520

Published by pirateguillermo

I play the bagpipes. I program computers. I support my family in their various endeavors, and I enjoy my wonderful life.

One thought on “Prime Factorization – Actual Code

Leave a Reply