Geeks 面试题之Ugly Numbers

Geeks 面试题之Ugly Numbers2015-09-26

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.

Write a program to find and print the 150′th ugly number.

METHOD 1 （Simple）

Thanks to Nedylko Draganov for suggesting this solution.

Algorithm:

Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.

To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.

For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.

下面是这个简单方法，这里带了可以打印所有小于n的ugly number的程序：

int maxDivide（int num, int div）{while （num % div == 0）{num /= div;}return num;} bool isUgly（int num）{num = maxDivide（num, 2）;num = maxDivide（num, 3）;num = maxDivide（num, 5）;return num == 1？ true:false;} int getNthUglyNo（int n）{int c = 0;int i = 0;while （c < n）{if （isUgly（++i）） c++;}return i;}#include <vector>using std::vector;vector<int> getAllUglyNo（int n）{vector<int> rs;for （int i = 1; i <= n; i++）{if （isUgly（i）） rs.push_back（i）;}return rs;}