Post Reply 
(PC-1211) Prime Factor Decomposition
03-21-2021, 03:46 PM (This post was last modified: 03-24-2021 03:21 PM by SlideRule.)
Post: #1
(PC-1211) Prime Factor Decomposition
An excerpt from Science and Engineering Sourcebook, pages 29-30:

One of the first problems facing a student is the prime factor decomposition of an integer. Recent applications of prime number decomposition lay in many areas including cryptography. Some of the modern codes are based on the assumption that it is extremely difficult, even for large computers, to find prime factors of large numbers. If a code is based on a key which is a product of two large primes, which it would take years for a large computer to find, then the code is for all practical purposes unbreakable.
   Two principal methods for finding prime factor of an integer are the Eratosthenes sieve, named after a famous Greek mathematician, and a simple odd divisor check. The first method is faster but also more appropriate for large computers, as it stores in memory all successive primes less than the square root of the number to be decomposed for testing of that number. The second method is much simpler as it only checks for decomposition into 2, 3, 5 and the successive odd integers. Though this approach is somewhat wasteful on execution time, as it checks against all odd but not necessarily prime integers, the second method imposes low memory requirements on the computer, as no intermediate results have to be stored. The second method is therefore uniquely applicable to solving on the Pocket Computer, and is the basis for the following program.

  30: IF (A=INT A)*(A>1)*(A<E 10)THEN 50
  50: E=A/2:C=2
  60: IF (E<>INT E)+(2E<>A)THEN 80
  70 :GOSUB 160:GOTO 50
  80: D=D+1:C=1+2D:IF C> √ATHEN 110
  90: E=A/C:IF (E<>INT E)+(EC<>A)THEN 80
100: D=D-1:GOSUB 160:GOTO 80
110: IF A>1LET A=A:K=K+1:A(26+K)=A:PAUSE A
120: BEEP 2:PRINT F;",# FACTORS= ";K
130: FOR I=1TO K
140: G=A(26+I):PRINT "FACT# ";I;"=";G
150: NEXT I:GOTO 120
170: K=K+1:A(26+K)=C

Press Shift Z to initialize the program, then follow the prompts to enter the number to be decomposed into prime factors. The program flashes the prime factors as they are found. Up to 130 prime factors are also stored for later display. The program terminates when the divisor is larger than the square root of the number to be decomposed by displaying the total number of prime factors found. The computer also beeps twice when the factorization is completed. Pressing the Enter key successively displays then all prime factors stored in memory.

Decompose 12345 into prime factors.
KEY-IN          DISPLAY                                REMARKS                               
                  ENTER NUMBER?
12345 Ent     3.                                        Each factor flashes
                  5.                                        briefly
                  12345. # FACTORS = 3.           Beeps twice
ENT             FACT# 1. = 3.                        Displays from memory
ENT             FACT# 2. = 5.
ENT             FACT# 3. = 823
ENT             FACT#12345 #FACTORS = 3.    Repeats display


ps: correction made
Find all posts by this user
Quote this message in a reply
03-23-2021, 03:43 PM
Post: #2
RE: (PC-1211) Prime Factor Decomposition
I think
should be

Find all posts by this user
Quote this message in a reply
03-23-2021, 06:16 PM (This post was last modified: 03-23-2021 06:20 PM by C.Ret.)
Post: #3
RE: (PC-1211) Prime Factor Decomposition
Another strange line due to its useless affectation "A=A" is :
110: IF A>1LET A=A:K=K+1:A(26+K)=A:PAUSE A

Which may be replace by a shorter code:
110: IF A>1LET C=A:GOSUB 160

Memorizing all the factors is a good idea, the user just have to wait for the two 'bips' and all the factors are listed with no delay.

Here is the version of I have used in the 80's when I was a child at middle school.


6 GOSUB 1:D=6-D:GOTO 6

In DEF mode:
>                           129211200 [shift][ N ]
          2.          6.    [ ENTER ]
          3.          4.    [ ENTER ]
          5.          2.    [ ENTER ]
\( 129211200 = 2^6 \times 3^4 \times 5^2 \times 997 \)

This is quite a shorter listing than the one propose by SlideRule, but the user have to wait for all factors to be displayed until the last one with the final '.END'

Also, there is no 'beeps' since they were forbidden in class and during examinations.

Also note the accelerating wheel (the D variable) which is alternatively +2 and +4 increments after factor 5.
Find all posts by this user
Quote this message in a reply
Post Reply 

User(s) browsing this thread: 1 Guest(s)