there's a problem when dealing with prime factorization-CodePudding

I've done this exercise, it was about finding if a number is "ugly" or not. A number is ugly if it has only 2, 3, or 5 as factors. otherwise, it's not ugly.

this is my solution:

include <stdbool.h>
#include <math.h>
bool is_prime(unsigned int num) {
    bool result = false;
    for (unsigned int i = 2; i <= sqrt(num); i  ) {
        if (num % i == 0) {
            result = false; 
        }
        else {
            result = true; 
            
        }
    }
    return result; 
}


bool is_ugly(unsigned int num) {
    bool result = false; 
    for (unsigned int i = 1; i <= num; i  ) {
        if (num % i == 0) {
            if (is_prime(i)) {
                if (i != 2 || i != 3 || i != 5) {
                    result = false; 
                    break; 
                }
                else {
                    result = true; 
                    break; 
                }
            }
        }
    }
    return result; 
}


int main(void) {

    bool result = is_ugly(30); // it must return true;  
    return 0; 
}

is_ugly function works like this:

it finds a factor and then it uses is_prime function to find if it's a prime factor. Then, I've thought that if the final number isn't equal to 2 or 3 or 5 (it's boolean logic), then it's false, because that means there is at least another number and it makes the initial expression (recall, A number is ugly if it has only 2, 3, or 5 as factors.) false. But it doesn't work, because when I run the algorithm with 30 it returns false, when it should've returned true because 30 = 2 * 3 * 5. Why?

CodePudding user response：

Your approach is too complicated.

All you need is to check whether a number contains only divisors 2, 3 and 5.

So the function is_prime is just redundant. Moreover it has a bug because for the number 2 it returns false.

The function is_ugly can look very simply. For exampele

bool is_ugly( unsigned int n ) 
{
    if ( n != 0 ) 
    {
        n = max_divide( n, 2 );
        n = max_divide( n, 3 );
        n = max_divide( n, 5 );
    }

    return n == 1'
}

In turn the called function max_divide can look the following way

unsigned int max_divide( unsigned int n, unsigned int divisor ) 
{
    if ( n != 0 ) 
    {
        while ( n % divisor == 0 ) 
        {
            n /= divisor;
        }
    }

    return n;
}