Creating a string of the prime factorization of a number (with exponents)

Question

So I have a program that creates a binary tree of the prime factors of a user input number and displays them in a treeView control:

Example One

Example Two

Now I would like to create a string like the ones shown in the messageboxes, except with exponents ("256 = 2 ^ 8", "1234567890 = 2 X 3 ^ 2 X 5 X 3607 X 3803")

My current code looks like:

private void LabelDisplayCondensed(FactorTreeNode currentNode)
{
    string result = Convert.ToString(root.Key) + " = " 
                    + Convert.ToString(currentNode.Left.Key);
    FactorTreeNode prevNode = currentNode;
    int exponent = 1;
    while (currentNode.Right != null)
    {
        prevNode = currentNode;
        currentNode = currentNode.Right;
        if (currentNode.Left.Key == prevNode.Left.Key)
        {
            exponent += 1;
        }
        else
        {
            exponent = 1;
        }
        if ((exponent != 1) && (currentNode.Left.Key != prevNode.Left.Key))
        {
            result += " ^ " + exponent + " X " + currentNode.Left.Key;
        }
    }
    MessageBox.Show(result);
}

This is my latest, desperate attempt. The function is called with the root of the tree. I realize this code is completely flawed. The current wall I am hitting is the currentNode reaches the right-most child in the tree, evaluates the key for its .Left.Key in

if (currentNode.Left.Key == prevNode.Left.Key) 

and crashes because .Left is null.

I was actually a lot closer earlier. I had it at a point where 500 would be evaluated to "500 = 2 ^ 2 X 5 ^ 2 ^ 2" I think (rather than the ideal 500 = 2 ^ 2 X 5 ^ 3)

Here is the code for my FactorTreeNode:

class FactorTreeNode
    {
        // constants

        // variables
        private long data;           // this is our only data, so also key
        private FactorTreeNode leftPointer;
        private FactorTreeNode rightPointer;
                                        // these pointers point to the
                                        // left and right children respectively
        private FactorTreeNode parentPainter;
                                        // pointer to the parent of the node

        // constructors
        public FactorTreeNode(long newValue)
        {
            Key = newValue;
            Left = null;
            Right = null;
            Parent = null;
        }

        // Properties
        public long Key
        {
            get
            {
                return data;
            }
            set
            {
                data = value;
            }
        }

        public FactorTreeNode Left
        {
            get
            {
                return leftPointer;
            }
            set
            {
                leftPointer = value;
            }
        }

        public FactorTreeNode Right
        {
            get
            {
                return rightPointer;
            }
            set
            {
                rightPointer = value;
            }
        }

        public FactorTreeNode Parent
        {
            get
            {
                return parentPainter;
            }
            set
            {
                parentPainter = value;
            }
        }
    }

I've been chewing on this all day. I appreciate any help.

Answer 1

Assuming your FactorTreeNodeclass is something like this:

class FactorTreeNode
{
    public FactorTreeNode(long key) { this.Key = key; }
    public FactorTreeNode Left { get; set; }
    public FactorTreeNode Right { get; set; }
    public long Key { get; private set; }
}

Then this will work:

private void LabelDisplayCondensed(FactorTreeNode root)
{
    string result = Convert.ToString(root.Key) + " =";

    long prevFactor = 0;
    int exponent = 0;
    bool firstFactor = true;
    FactorTreeNode currentNode = root;
    while (currentNode != null)
    {
        long nextFactor = currentNode.Left == null ?
            currentNode.Key :
            currentNode.Left.Key;
        if (nextFactor != prevFactor && prevFactor != 0)
        {
            result += WriteFactor(prevFactor, exponent, ref firstFactor);
            exponent = 1;
        }
        else
        {
            exponent++;
        }

        prevFactor = nextFactor;
        currentNode = currentNode.Right;
    }

    result += WriteFactor(prevFactor, exponent, ref firstFactor);
    MessageBox.Show(result);
}

private string WriteFactor(long factor, int exponent, ref bool firstFactor)
{
    string result = firstFactor ? " " : " X ";
    firstFactor = false;
    if (exponent == 1)
    {
        result += factor.ToString();
    }
    else
    {
        result += factor.ToString() + " ^ " + exponent.ToString();
    }

    return result;
}

Obviously this includes no checks that the tree is valid.

You probably also want to use StringBuilder to actually build the string rather than doing all those appends.

Answer 2

From what it seems, you are running down the tree, and checking to see if the current value equals the previous one, in order to figure out how many times a factor appears.

What happens when you have 3x3x37 ? you start with 3, next iteration you have 3, so you increment the exponent, and next iteration you have 37, so you set exponent to 1...

You need to have a logic that goes something like

• Look at current node, if it same as prev node
  • increase exponent, repeat until you find a different node
• Print the node with the exponent if it's not 1

I'm assuming your nodes are ordered otherwise you'll have to put some more effort in there, but either way, you need to add to the string the value of x even when it doesn't have the exponent > 1, which it seems you're failing to do ATM.

Answer 3

would you try this approach

private void LabelDisplayCondensed(FactorTreeNode currentNode)
    {
        string result = Convert.ToString(root.Key) + " = " + Convert.ToString(currentNode.Left.Key);
        FactorTreeNode prevNode = currentNode;
        int exponent = 1;
        while (currentNode.Right != null && currentNode.Left!= null)
        {
            prevNode = currentNode;
            currentNode = currentNode.Right;
            if (  currentNode.Left.Key == prevNode.Left.Key && currentNode.Right != null )  //updated *****************
            {
                exponent++;
                continue;
            }
            else if (exponent != 1 )
            {
                result += " ^ " + exponent ;
                exponent = 1;

            }

                result += " X "  + currentNode.Left.Key;
        }
        MessageBox.Show(result);
    }