(PC-1211) Prime Factor Decomposition - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: Not HP Calculators (/forum-7.html) +--- Forum: Not remotely HP Calculators (/forum-9.html) +--- Thread: (PC-1211) Prime Factor Decomposition (/thread-16509.html) (PC-1211) Prime Factor Decomposition - SlideRule - 03-21-2021 03:46 PM 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)*(AINT 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 RE: (PC-1211) Prime Factor Decomposition - pyedog - 03-23-2021 03:43 PM I think Code:  10: "Z*CLEAR :PAUSE "PRIME FACTOR FINDER":USING should be Code:  10: "Z"CLEAR :PAUSE "PRIME FACTOR FINDER":USING Thanks! RE: (PC-1211) Prime Factor Decomposition - C.Ret - 03-23-2021 06:16 PM 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.