cprimesfunction-definitionfactorshamming-numbers

# there's a problem when dealing with prime factorization

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?

Solution

• 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;
}
``````