Programs: 
FACTOR, 1FACTOR, NEXTFACT 

Version: 
4.0, 5 May 2002 

Description: 
These programs find the prime factors of a number. The program NEXTFACT can be called by a program. The program FACTOR is a user interface to the NEXTFACT program. The program 1FACTOR is a subroutine to FACTOR. 

Compatibility: 


Other programs 
Every positive integer is the product of a number of prime numbers. A prime number is a number that is evenly divisible only by itself and the number 1. Other numbers are called composite. The first few prime numbers are 2, 3, 5, 7, 11, and 13. The number 4, for example, is the product of 2 and 2, and so is not prime, or is composite. The number 10 is the product of 2 and 5, and so is not prime.
The prime factorization of a number is the list of prime factors of a number. The mutiplicity of a prime factor is the number of times it appears in the prime factorization. The multiplicity of 3 as a factor of 18, for example, is two — 18 is 2 times 3 times 3, so the prime 3 appears twice in the list of prime factors of 18.
The program NEXTFACT accepts a number and a lower bound on candidate factors, and finds the smallest number at least as great as the lower bound that is a factor of the number. The number for which a factor is to be found must be put into A, and the lower bound on the factor must be put into B. NEXTFACT finds the first number that is B or greater that divides A, places that number into B, and the quotient into A. Thus, a number may be completely factored by putting the number into A and repeatedly calling NEXTFACT until the value 1 appears in A.
The program FACTOR accepts a number from the user, calls NEXTFACT repeatedly to find its factors, and displays these factors and their multiplicities on the display.
Just about everyone has a program that factors through trial division, which is the algorithm this program uses. The advantage of this program is that the factor search program is callable, rather than embedded in a user interface.
Load the programs FACTOR, 1FACTOR, NEXTFACT, and VRPRE.
If you want to factor a number in a program, put the number into the variable A, put a zero into the variable B, and call NEXTFACT. The smallest factor of A will be placed into D, and the quotient of the number placed into A and the factor in D will be placed into C. You can them move the quotient into A and the factor into B, and repeat the call, until the quotient obtained is 1. At that point, the value in D is the highest factor of the original value of A. If the value of the quotient in C is 1 after the first call to NEXTFACT, then A was prime.
The program FACTOR uses the program NEXTFACT to factor a number. FACTOR prompts for the number to be factored with the line:
Number?
Enter the number to be factored and press EXE. For each factor found, FACTOR will display the line:
Factor
followed by the value of the factor, and the line:
Multiplicity
followed by the multiplicity of the factor.
The programs are available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, and is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.
Program FACTOR (170 bytes):
; Program FACTOR ; ; Description: ; Extracts all factors from a number. ; ; Variables: ; A: Used for communications with subroutines ; B: Used for communications with subroutines ; C: Used for communications with subroutines ; D: Used for communications with subroutines ; E: Used for communications with subroutines ; F: The current number to factor ; G: The current (not yet reported) factor ; H: The multiplicity of the current factor ; I: The quotient of the current number to factor and the newly ; found factor ; J: The newly found factor ; ; Calling sequence: ; None; main program. ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; List 6: the variable save stack. ; Z: the stack pointer for the variable save stack. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; => is conditional jump ; <> is not equals relational Prog "VRPRE" ; Set up variable save stack While 1 ; Infinite loop getting numbers to factor "Number"?>F ; Ask for number to factor Abs Int F>F ; Ensure it is a positive integer 0>G ; Zero current factor 0>H ; Zero current multiplicity Do ; Repeat until all factors extracted F>A ; Get current number to factor G>B ; Start at current factor Prog "NEXTFACT" ; Get the next factor C>I ; Save the quotient D>J ; Save the factor G=0=>J>G ; If no factor was yet found, use this factor If G<>J ; If the found factor is not the current factor Then G>A ; Get the current factor H>B ; Get its multiplicity Prog "1FACTOR" ; Report it to the user J>G ; Set the current factor to the new one 0>H ; Set the multiplicity to zero IfEnd ; [End of found factor not current factor] H+1>H ; Increment factor multiplicity I>F ; Quotient is now to be factored LpWhile F<>1 ; [End of repeat until all factors extracted] G>A ; Get the last factor H>B ; And its multiplicity Prog "1FACTOR" ; Report it WhileEnd ; [End of infinite loop getting numbers to factor]
Program 1FACTOR (45 bytes):
; Program 1FACTOR ; ; Description: ; Reports a factor and its multiplicity on behalf of FACTOR. ; ; Variables: ; A: The factor to be reported ; B: The multiplicity to be reported ; ; Calling sequence: ; {factor}>A ; {multiplicity}>B ; Prog "1FACTOR" ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; None. ; ; Side effects: ; Displays "Factor", the value of A, "Multiplicity" and the value of ; B ; ; Symbols used: ; _ is display triangle "Factor" A_ "Multiplicity" B_
Program NEXTFACT (90 bytes):
; Program NEXTFACT ; ; Description: ; Finds the smallest factor greater than or equal to a specified ; value of a specified number. ; ; Variables: ; A: The number for which a factor is to be found ; B: The smallest value of the factor to be found ; C: The quotient of the number in A and the factor found [output] ; D: The factor found [output] ; ; Calling sequence: ; {number to factor}>A ; {smallest factor value}>B ; Prog "NEXTFACT" ; C>{quotient} ; D>{factor} ; ; Note: if the smallest factor value is specified as 0, the value 2 ; is assumed. Thus, to find the smallest factor, place 0 into B. ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; None. ; ; Side effects: ; None. ; ; Symbols used: ; > is assignment arrow ; => is conditional jump ; / is division operator ; <> is not equal to relational ; x^2 is square operator Abs Int A>C ; Normalize number to factor into C Abs Int B>D ; Normalize proposed factor into D D<2=>2>D ; Ensure 2 is the smallest factor asked for While DInt (C/D)<>C; Loop until a divisor found If Dx^2>C ; If we have searched past the square root Then C>D ; then there is no divisor Else 2D+12Int (D/2)>D; otherwise advance to next odd number IfEnd ; [End of test for search past the square root] WhileEnd ; [End of loop until divisor found] C/D>C ; Place quotient into C
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.