Author: Theodore Odeluga
This is a Node command line project and Node.js can be downloaded from here
Instructions for running a command line program with Node.js can be found here
The source files for this project can be downloaded from here
In this tutorial, were going to run an interesting exercise you’ve probably seen in several different examples exploring ways to tackle the problem of prime factorisation.
Prime factorisation typically takes an integer and finds, if any are to be found, all the prime factors of a given number.
While on the one hand, the rule of primes is pretty straightforward (a prime number is only divisible by 1 and itself), producing a pattern in code that consistently reflects this is potentially non-trivial.
One difficulty is setting a distinction which acknowledges that while most prime numbers are odd (the exception is 2) not all odd numbers are prime.
In the following solution as you’ll see, there is a way to simplify the logic for an algorithm that derives a number’s prime components and not end up with something too obscure or convoluted.
At this point, I don’t mind admitting I only arrived at the method described below after no small amount of trial and error.
What I ended up learning – or re-learning (from examples seen elsewhere) is that prime factorisation (in code) is a two-step process.
First, one needs to factorize a dividend (the integer in question), then try to “factorize the factors” of the dividend as they are generated, to ascertain if they are prime.
If this all sounds a bit strange, it’ll be clear very soon.
While I experimented, I came up with a rough and ready prototype that only worked about 80% of the time.
The aha moment came when I realized the problem wasn’t necessarily about trying to recreate the methodology in code so much as removing the unnecessary complication of initially trying to combine general factorisation with prime factorisation.
Separating these two essential operations was all I needed to make things easier.
I ended up with something of an object-oriented design. Here it is.
The first step is to simply define the class.
class PrimeFactors {
constructor(){
}
factorisation (mynumber){
let i = 0;
let factors = [];
while(i < mynumber){
i++;
if(mynumber % i == 0){
factors.push(i);
}
}
if(factors.length > 2){
console.log(mynumber + " is not prime. ");
}
if(factors.length == 2) {
console.log(mynumber + " is prime. ");
}
}
}
PrimeFactors contains one method – factorisation.
As expected by the name, factorisation takes the integer passed to it (mynumber) and proceeds to break it down.
Following the creation of an iterator and empty array, factorisation tests every number less than mynumber for equal divisibility against mynumber.
If the result of any division is itself an integer, this is placed into the factors array.
The process continues until the limit is reached as determined by the dividend.
The next step tests if the number of elements contained in the factors array is more than two.
If so, this means the factor currently being processed (mynumber in broken down form) is not prime.
If the resulting number of elements or “sub-factors” in the factors array is exactly two, then the factor being tested at that point is a prime number.
Once the main functionality is established, the second half of the program simply runs it repeatedly through a loop.
let primes = new PrimeFactors();
let methodcalls = [];
let dividend = 500;
let two = 2;
let k;
let j = 1;
if(dividend % two == 0){
console.log(two + " is prime. ");
}
for(k = 0; k < dividend; k++){
j += 2;
if(dividend % j == 0){
methodcalls[k] = primes.factorisation(j);
}
}
Here’s the entire program for convenience.
class PrimeFactors {
constructor(){
}
factorisation (mynumber){
let i = 0;
let factors = [];
while(i < mynumber){
i++;
if(mynumber % i == 0){
factors.push(i);
}
}
if(factors.length > 2){
console.log(mynumber + " is not prime. ");
}
if(factors.length == 2) {
console.log(mynumber + " is prime. ");
}
}
}
let primes = new PrimeFactors();
let methodcalls = [];
let dividend = 500;
let two = 2;
let k;
let j = 1;
if(dividend % two == 0){
console.log(two + " is prime. ");
}
for(k = 0; k < dividend; k++){
j += 2;
if(dividend % j == 0){
methodcalls[k] = primes.factorisation(j);
}
}
Conclusion
Admittedly, the code could do with a bit of optimization but the verbosity of the finished product is deliberate in this case, to simply make clear what the algorithm is doing, by spelling everything out. I hope it’s a useful and helpful way of doing things. Try the functionality out with different values and see how you might streamline it. Thanks for reading and do please come back again soon.