题目

有一些数的素因子只有3、5、7，请设计一个算法，找出其中的第k个数。

给定一个数int k，请返回第k个数。保证k小于等于100。

测试样例：

3

返回：7

解法

主要就是在于isPrime这个函数的判断上，只能有3、5、7这三个素因子，不能有11这样的；所以就可以建立一个循环来判断，首先肯定不会为偶数，偶数全部排除。在奇数中，如果有3这个因子，就先x=x/3，因子5、7也是同样的方法，如果除之后发现x为1了说明确实只有3、5、7因子中的一个或几个；但如果发现除了一圈下来还是原来的数，就说明肯定有其他因子，返回false。代码如下:

class KthNumber {

public:

    bool isPrime(int x)

    {

        if(x%2==0)

            return false;

        else{

            while(1)

            {

                int temp=x;

                if(x%3==0) x=x/3;

                if(x%5==0) x=x/5;

                if(x%7==0) x=x/7;

                if(x==1) return true;

                if(x==temp)

                    return false;

            }

        }

    }

    int findKth(int k) {

        // write code here

        int i=0,j=3;

        while(i!=k)

        {

            if(isPrime(j))

                i++;

            j++;

        }

        j--;

        return j;

    }

};

巴特西

CC38:第k个数

题目

解法

最新文章

热门文章