Prime Factor Tree Algorithm

prime-factor-tree-150The Prime Factor Tree is a visual technique used in Maths to workout all the prime factors of a large number.

tree-leaf With this approach, all the leaf nodes (nodes without sub-branches) are the prime factors of the root node. For instance, with the above tree, the prime factors of 150 are 2, 3, 5 and 5 again. In other words:

150 = 2 x 3 x 5 x 5 = 2 x 3 x 52

We have decided to create our own Prime Factor Tree Algorithm to build a binary tree structure to store all the prime factors of any given root number.

The aim of this challenge is to demonstrate one way to implement a Binary Tree Structure in Python using a very basic Node Class.

#A class to implement a Node / Tree
class Node:
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

With this approach, a Tree is in fact just a Node (a root Node)!
Here is how we could create a basic prime factor tree for number 10 = 2 x 5:

tree = Node(10)
tree.left = Node(2)
tree.right = Node(5)

We then added two additional methods to our Node Class:

  1. The drawTree() method is used to draw the tree on screen. It’s based on a complex algorithm that we imported from the module.
  2. The buildPrimeFactorTree() method is used to recursively add branches/sub-nodes to our root tree to build the Prime Factor Tree progressively.

Here is the full implementation of our Prime Factor Tree Algorithm in Python:

Did you like this challenge?

Click on a star to rate it!

Average rating 4.6 / 5. Vote count: 5

No votes so far! Be the first to rate this post.

As you found this challenge interesting...

Follow us on social media!

Tagged with: