未分類

Ugly Number

Go, LeetCode, Math

Ugly Number

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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

提示 解題應用
Math 規律觀查

Default:

1
2
3
func isUgly(num int) bool {
}

解答思路:

要判斷一數字是否僅由2、3、5所組成，最快的方式就是不斷的將該數利用回圈去除2、3、5，且各別除以時其餘數必須為0(因為是由2、3、5組成)，最後剩下的數如果為1表示其完全由2、3、5所組成為Ugly Number，如果不為1那麼就勢必存在著其它的質數回傳false。

程式碼解說:

首先要將0這個例外給剔除掉回傳false，接著用flag來確定該數能否被2、3、5整除，如果有其一能被整除，就將該數除以其一接著再重新在判斷一次，直到完全不能被2、3、5整除(含其它質數)或該數為1(被完全整除)為止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if num == 0 {
	return false
}
flag := true
for flag {
	flag = false
	if num%2 == 0 {
		flag = true
		num = num / 2
	}
	if num%3 == 0 {
		flag = true
		num = num / 3
	}
	if num%5 == 0 {
		flag = true
		num = num / 5
	}
}

該數被完全拿掉2、3、5的組成要素後，最後再判斷剩下的值是否為1(被完全整除)，如果是就回傳true，否則回傳false

1
2
3
4
if num != 1 {
	return false
}
return true

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func isUgly(num int) bool {
	if num == 0 {
		return false
	}
	flag := true
	for flag {
		flag = false
		if num%2 == 0 {
			flag = true
			num = num / 2
		}
		if num%3 == 0 {
			flag = true
			num = num / 3
		}
		if num%5 == 0 {
			flag = true
			num = num / 5
		}
	}
	if num != 1 {
		return false
	}
	return true
}

總結:

判斷一數字是否由某些特定的質數所組成，最快的方式就是不斷的將該數個別除以特定的質數，且若為組成的要素其餘數必為0，最後剩下的數如果為1表示其完全由該質數組成為Ugly Numer。

分享到