Previous page Next page Navigation bar

Programs

Mathematics Programs

Factorization

Summary

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:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

VRPRE

Detailed Description

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.

Other Programs

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.

Usage

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.

Program Source

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+1-2Int (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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 5 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data