Prime Factorisation

[Flaze07]

...
this code isnt working for some reason that I have yet to know...
anyways...(it worked for some numbers)

#include <iostream>
#include <cmath>
#include <string>
#include <vector>

bool IsPrime(int val)
{
    for(int i = 2; i <= val / 2; ++i)
    {
        if(val % i == 0)
        {
            return false;
            break;
        }
    }
    return true;
}

bool PrimeFactorisation(int val, std::vector <int> &result)
{
    if (IsPrime(val) == true) return false;
    while (IsPrime(val) == false)
    {
        for (int i = 2; i < 10; ++i)
        {
            if ((IsPrime(i) == true) && (val % i == 0))
            {
                val /= i;
                result.push_back(i);
                break;
            }
        }
    }
    return true;
}

int main()
{
    std::vector <int> output;
    int input;
    std::cout << "enter a number\n";
    std::cin >> input;
    if (PrimeFactorisation(input, output) == false) std::cout << "it is a prime number";
    else if (PrimeFactorisation(input, output) == true)
    {
        for (int i = 0; i < output.size(); ++i)
        {
            std::cout << output.at(i);
            if (i == output.size() - 1) break;
            else std::cout << " X ";
        }
    }
    std::cin.ignore();
}

[ne555]

the prime factorization of a prime number is that same number.
For example: 2 -> {2}.
Because you return from the function when `val' is prime, you always miss one factor.

`PrimeFactorisation()' has side effects on its parameters. You call that function twice, so you end with the factors duplicated.
It seems that you don't understand what else means:

Otherwise; in the other, or the contrary, case; if the facts were different.

you shouldn't check the opposite condition.


Also, I find IsPrime(val) == false hard to read. Comparing against a bool seems like a conceptual error, and comparing against `false' is quite less clearer than negating
not IsPrime(val)

[Flaze07]

Thanks..

[ElusiveTau]

Hi,

Your algorithm for finding the prime factorization of a number val checks for divisibility with prime numbers that are less than 10 (i.e., 2, 3, 5, 7). What if val were a number divisible by a prime number greater than 10?

For instance, if val=121, your for loop wouldn't check against the prime number 11 and so 11 wouldn't be pushed into the vector (but you will agree that it IS part of the prime factorization of 121). In fact, your function will not return the correct prime factorization for any val whose prime factorization consists of primes greater than 10.