Prime Number Factorization with Small Basic
Scope
In this brief article, we'll consider a simple method to factorize a number into its prime factors. We'll use Small Basic for our means, which can be downloaded at http://smallbasic.com/. Once installed, we will be ready to go.
Factorization
Before we begin developing our solution, it could be useful to spend some preliminary words about what we will implement, i.e. what factorization is, and why we could/should care about it. Factorization, in mathematical language, is the process through which we take an object (like a number, a polynomial, etc.) and decompose it to a product of subparts, that will form our original object when multiplied. The factorization of integer numbers is a complex problem because it is difficult to complete it in reasonable times, when the given number is very large. In widely known security algorithms, such as RSA, that computational complexity is what the algorithm is primarily about: in fact, the public key a user can create with RSA is based upon two prime numbers (which must remain secret), and breaking a RSA key ultimately means to be able to factorize it. For an explanation about that topic, you could refer to Integer factorization and RSA problem.
Integer factorization resides on the fundamental theorem of arithmetic.
Prime numbers
An integer number can be defined prime when its only divisors are 1 and the number itself. If that condition isn't satisfied, what we have it's what's called a composite number. Prime numbers have various applications outside the field of pure mathematics, a good example of which we've seen above, speaking about cryptography.
Fundamental Theorem of Arithmetic
The fundamental theorem of arithmetic states that every integer number greater than 1 its either prime itself, or is the product of prime numbers, and that this product is unique. For example, the number 2500 is the product of 2 * 2 * 5 * 5 * 5 * 5 (or 2^2 * 5^4), while 31 is prime itself.
Check for primality
To check for primality, the first thing that comes up to mind is to test a number against all its predecessor, to find out if it's divisible only for itself and 1. If that kind of approach can be pretty straightforward in case of relatively small numbers, think about what will happen in case we want to check a number with many thousands of digit. Leaving alone all the discussions and algorithms mathematics have produced to simplify the problem, a general rule tell us to check only the divisors up to Sqrt(n).
The reason for that is simple: if a number n is not a prime, it can be factored as a product of p * q. If those factors are greater than the square root of n, that means the product p * q will be greater than n too. One of the two factor (at least) must be then smaller than the square root of n, so we need to test only factors which are smaller or equal to the square root.
Wrap it up
Now that we've covered up (more or less) the theory, we can sum up what our program will need to do. We can divide it into the following steps:
- Ask the user for a number to be factorized
- Starting from the value of two as a divisor, we check for the primality of the divisor itself
- If our number is divisible for the current divisor, then the divisor (which is a prime) is a factor of our number
- If not, we increase the divisor and test again for its primality, repeating the loop
Lets see how we can implement such a flow with Small Basic.
Requesting input
As we've preiously stated, we need to ask the user what is the number to factorize. At the same time, we need to initialize some other variables we'll use in our program.
StartProgram:
TextWindow.Write("Enter a number to factorize: ")
number = TextWindow.ReadNumber()
If number = 0 Then
Goto EndProgram
EndIf
TextWindow.WriteLine("")
divisor = 2
factors[0] = 0
index = 0
TextWindow.ReadNumber() method will wait for the user to enter a number, storing its value into the number variable. If the number is zero (or no inputs are given) the program will exit. Other declared variables are divisor, initialized to 2, factors array, that will be used to store each found prime factor, and index, which will serve to increment position into the factors array. More on this later
Calculate primality
We've seen above that to check if a number is prime, we need to test its divisors up to the square root of the number itself. We must test each of those divisors, checking if the division give back no remainders. That can be done as follows:
' -- Test for primality of current divisor
isPrime = 1
For i = 2 To Math.SquareRoot(divisor)
If Math.Remainder(divisor, i) = 0 Then
isPrime = 0
Goto EndPrime
EndIf
EndFor
EndPrime:
Pretty self-explanatory: we test our current divisor against all its possibile divisors up to the square root of itself. The isPrime variable will store the result of our test.
Spotting factors
Having determined our current prime divisor, we can test it against our number. If the outcome finds a factor, we will proceed in storing it into our factors array, reducing our initial number dividing it for the divisor. The operation will going on until our number hasn't been cut down to 1. In case our divisor returns a remainder, we will increase it, and execute another primality test
'-- Check if current divisor (which is a prime number) divides the numerator with no remainder
If isPrime = 1 And Math.Remainder(number, divisor) = 0 Then
factors[index] = divisor
index = index + 1
number = number / divisor
divisor = 2
Else
divisor = divisor + 1
EndIf
Showing results
Now we want to show to the user our factorization expression. To mantain a concise representation of our result, i've chose to write it as a product of powers (like the 2^2 * 5^4 seen above). Lets see how.
'-- Write to TextWindow our factors' expression: if a certain factor is recurrent, its power will be shown
power = 1
For i = 0 To Array.GetItemCount(factors)
If i > 0 And factors[i] = factors[i-1] Then
power = power + 1
Else
If power > 1 Then
TextWindow.Write("^" + power + " ")
power = 1
EndIf
EndIf
If i = 0 Or (i>0 And factors[i] <> factors[i-1]) Then
If i > 0 And i < Array.GetItemCount(factors) Then
TextWindow.Write(" * ")
EndIf
TextWindow.Write(factors[i])
EndIf
EndFor
For every element stored in our factors array, we check if its predecessor has the same value. In case the test is positive, we increase a variable named power, which will represent the power of the number itself. When the current factor is different from the previous, we could write it in the output console, with its power as well.
A sample session can be as follows:
Source code
The complete source code is the following:
' Factorize Numbers
' -----------------------------------------------------------------------------------
StartProgram:
TextWindow.Write("Enter a number to factorize: ")
number = TextWindow.ReadNumber()
If number = 0 Then
Goto EndProgram
EndIf
TextWindow.WriteLine("")
divisor = 2
factors[0] = 0
index = 0
TextWindow.WriteLine("Factorizing...")
TextWindow.WriteLine("--------------------")
'-- Loop until our number hans't been reduced to 1
While number > 1
' -- Test for primality of current divisor
isPrime = 1
For i = 2 To Math.SquareRoot(divisor)
If Math.Remainder(divisor, i) = 0 Then
isPrime = 0
Goto EndPrime
EndIf
EndFor
EndPrime:
'-- Check if current divisor (which is a prime number) divides the numerator with no remainder
If isPrime = 1 And Math.Remainder(number, divisor) = 0 Then
factors[index] = divisor
index = index + 1
number = number / divisor
divisor = 2
Else
divisor = divisor + 1
EndIf
EndWhile
'-- Write to TextWindow our factors' expression: if a certain factor is recurrent, its power will be shown
power = 1
For i = 0 To Array.GetItemCount(factors)
If i > 0 And factors[i] = factors[i-1] Then
power = power + 1
Else
If power > 1 Then
TextWindow.Write("^" + power + " ")
power = 1
EndIf
EndIf
If i = 0 Or (i>0 And factors[i] <> factors[i-1]) Then
If i > 0 And i < Array.GetItemCount(factors) Then
TextWindow.Write(" * ")
EndIf
TextWindow.Write(factors[i])
EndIf
EndFor
'-- Clean factors array, and restart until number is void or zero
TextWindow.WriteLine("")
TextWindow.WriteLine("")
factors = ""
Goto StartProgram
EndProgram:
PNF on SmallBasic.com
The source code above is available for testing and download at: http://smallbasic.com/program/?LLS908