把只包含质因子2、3和5的数称作丑数

问题描述：

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

输入
7
输出
8

答


class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        // 0-6的丑数分别为0-6
        if(index < 7) return index;
        //p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
        int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
        vector<int> arr;
        arr.push_back(newNum);
        while(arr.size() < index) {
            //选出三个队列头最小的数
            newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));
            //这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
            if(arr[p2] * 2 == newNum) p2++;
            if(arr[p3] * 3 == newNum) p3++;
            if(arr[p5] * 5 == newNum) p5++;
            arr.push_back(newNum);
        }
        return newNum;
    }
};

答

#include<bits/stdc++.h>
using namespace std;
int n,sum;
bool isprime(int k){
    for(int d=1;d<=sqrt(k);d++){
        if(k%d==0) return 1;
    }
    return 0;
}
int main(){
    cin>>n;
    if(n==1){
        cout<<'1';
        return 0;
    }
    n--;
    for(int i=1;;i++){
        if(i%2==0||i%3==0||i%5==0){
            if(i%2==0){
                if(isprime(i%2)) continue;
            }
            if(i%3==0){
                if(isprime(i%3)) continue;
            }
            if(i%5==0){
                if(isprime(i%5)) continue;
            }
            sum++;
        }
        if(sum==n){
            cout<<i;
            break;
        }
    }
    return 0;
}

答

供参考：

#include<stdio.h>
#define min(x,y) ((x)>(y)?(y):(x))
__int64 UglyNumber(int n)
{
    __int64 UglyNum = 0, * m = new __int64[n];
    m[0] = 1;
    int a = 0, b = 0, c = 0;
    for (int i = 1; i < n; i++) {
        m[i] = min(min(m[a] * 2, m[b] * 3), m[c] * 5);
        if (m[i] == m[a] * 2) {
            a++;
        }
        if (m[i] == m[b] * 3) {
            b++;
        }
        if (m[i] == m[c] * 5) {
            c++;
        }
    }
    UglyNum = m[n - 1];
    delete []m;
    return UglyNum;
}
int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n >= 1 && n <= 10000)//输入 0  或 10001 结束 
    {
        printf("%I64d\n", UglyNumber(n));
    }
    return 0;
}

把只包含质因子2、3和5的数称作丑数

相关推荐