(PC-1211) Prime Factor Decomposition

[SlideRule]

An excerpt from Science and Engineering Sourcebook, pages 29-30:

DESCRIPTION
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.

PROGAM LISTING
  10: "Z"CLEAR :PAUSE "PRIME FACTOR FINDER":USING
  20: INPUT "ENTER NUMBER?";A:F=A
  30: IF (A=INT A)*(A>1)*(A<E 10)THEN 50
  40: BEEP 1:PAUSE "ERROR":GOTO 20
  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
160: PAUSE C:IF K>130RETURN
170: K=K+1:A(26+K)=C
180: A=E:RETURN

INSTRUCTIONS
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.

EXAMPLE
Decompose 12345 into prime factors.
                                                                                         
KEY-IN          DISPLAY                                REMARKS                               
Shift Z         PRIME FACTOR FINDER
                  ENTER NUMBER?
12345 Ent     3.                                        Each factor flashes
                  5.                                        briefly
                  823.
                  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

BEST!
SlideRule

ps: correction made

[pyedog]

I think

Code:

 10: "Z*CLEAR :PAUSE "PRIME FACTOR FINDER":USING

should be

Code:

 10: "Z"CLEAR :PAUSE "PRIME FACTOR FINDER":USING

Thanks!

[C.Ret]

Another strange line due to its useless affectation "A=A" is :

Code:

110: IF A>1LET A=A:K=K+1:A(26+K)=A:PAUSE A

Which may be replace by a shorter code:

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.

Code:

1 F=F+D,P=0:IF FF>NPRINT N,"END ":END
2 Q=N/F:IF Q=INT QLET N=Q,P=P+1:GOTO 2
3 IF PPRINT F,P
4 RETURN

5 "N"AREAD N:F=1,D=1:GOSUB 1:GOSUB 1:D=2:GOSUB 1
6 GOSUB 1:D=6-D:GOTO 6

In DEF mode:

Code:

>                           129211200 [shift][ N ]
          2.          6.    [ ENTER ]
          3.          4.    [ ENTER ]
          5.          2.    [ ENTER ]
        997.END

\( 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.