c - C 中的丑数逻辑

Question

继here之后，我正在尝试开发自己的逻辑来生成一系列丑陋的数字。但每次都会打印所有数字。

我正在确定数字的前 3 个质因数是否为 2、3 和 5，并将它们放入计数变量中，以确定数字 x 的质因数总数。

如果计数大于3，这个数字并不难看。

这是代码:

/* To generate a sequence of Ugly numbers 
   Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
   1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
   shows the first 11 ugly numbers. By convention, 1 is included.
*/

#include<stdio.h>
#include<math.h>

int isprime(int x)
{
    int i;
    for(i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}

int isUgly(int x)
{
    int count=0; //To maintain the count of the prime factors. If count > 3, then the number is not ugly
    int i;
    for(i=2;i<=sqrt(x);i++)
    {
        if(isprime(i) && x%i==0)
        {
            count++;
            if(count > 3)
                return 0; // Not ugly
        }   
    }
    return 1;
}

int main(void)
{
    int i,n=10;
    printf("\n The ugly numbers upto %d are : 1 ",n);
    for(i=2;i<=n;i++)
    {
        if(isUgly(i))
            printf(" %d ",i);
    }
    return 0;
}

Answer 1

这是一个似乎对我有用的 isUgly() 版本。

int isUgly(int x)
{
    int i;
    static int factors[] = {2, 3, 5};

    // Boundary case...
    // If the input is 2, 3, or 5, it is an ugly number.
    for ( i = 0; i < 3; ++i )
    {
       if ( factors[i] == x )
       {
          return 1;
       }
    }

    if ( isprime(x) )
    {
       // The input is not 2, 3, or 5 but it is a prime number.
       // It is not an ugly number.
       return 0;
    }

    // The input is not a prime number.
    // If it is divided by 2, 3, or 5, call the function recursively.
    for ( i = 0; i < 3; ++i )
    {
       if ( x%factors[i] == 0 )
       {
          return isUgly(x/factors[i]);
       }
    }

    // If the input not a prime number and it is not divided by
    // 2, 3, or 5, then it is not an ugly number.
    return 0;
}