(PC1211) Prime Factor Decomposition

03212021, 03:46 PM
(This post was last modified: 03242021 03:21 PM by SlideRule.)
Post: #1




(PC1211) Prime Factor Decomposition
An excerpt from Science and Engineering Sourcebook, pages 2930:
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=D1: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. KEYIN 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 

03232021, 03:43 PM
Post: #2




RE: (PC1211) Prime Factor Decomposition
I think
Code: 10: "Z*CLEAR :PAUSE "PRIME FACTOR FINDER":USING Code: 10: "Z"CLEAR :PAUSE "PRIME FACTOR FINDER":USING Thanks! 

03232021, 06:16 PM
(This post was last modified: 03232021 06:20 PM by C.Ret.)
Post: #3




RE: (PC1211) Prime Factor Decomposition
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 In DEF mode: Code: > 129211200 [shift][ N ] 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. 

« Next Oldest  Next Newest »

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