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
One thought on “Prime Factorization – Actual Code”