题目地址:https://leetcode.com/problems/ugly-number/open in new window

Total Accepted: 22335 Total Submissions: 67449 Difficulty: Easy

题目描述

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

1、 1istypicallytreatedasanuglynumber.;
2、 Inputiswithinthe32-bitsignedintegerrange:[−231,231−1].;

题目大意

如果一个数的因子只有2,3,5,那么这个数是丑数。判断一个数是不是丑数。

解题方法

除去2,3,5因子

把这个数中的所有的2,3,5的因子全部除去,剩余的数为1,则说明全部为这几个因子构成。

python解法。

class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0: return False
        while num % 2 == 0:
            num /= 2
        while num % 3 == 0:
            num /= 3
        while num % 5 == 0:
            num /= 5
        return num == 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Java解法:

public static boolean isUgly(int num) {
	if (num == 1) {
		return true;
	}

	while (num >= 2 && num % 2 == 0) {
		num = num / 2;
	}
	while (num >= 3 && num % 3 == 0) {
		num = num / 3;
	}
	while (num >= 5 && num % 5 == 0) {
		num = num / 5;
	}
	return num == 1;
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

另外有精简的答案如下。

public class Solution {
    public boolean isUgly(int num) {
        int[] divides ={2,3,5};
        for(int i = 0; i < divides.length && num > 0; i++){
            while(num % divides[i] == 0){
                num /= divides[i];
            }
        }
		return num == 1;
    }
}

1 2 3 4 5 6 7 8 9 10 11

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发