看了答案才发现&＃xff0c;这个题目这么简单。
这个题目隐含的意思很坑&＃xff0c;
除了2、3、5&＃xff0c;不能有别的质数了&＃xff0c;比如2x7 &＃61; 14&＃xff0c;7是质数&＃xff0c;不行。
2x25可以 因为25不是质数
所以我就想到
一个数&＃xff0c;看能否被2整除&＃xff0c;如果可以
1、这个商是质数吗&＃xff1f; 如果是质数&＃xff0c;那么是2、3、5吗&＃xff1f;是就是true&＃xff0c;不是就是false
2、如果不是质数&＃xff0c;就判断这个商是不是丑数。递归
后面对3和5也是这样处理。
首先是判断质数的方法
就是num%i 一直到根号nums
https://blog.csdn.net/huang_miao_xin/article/details/51331710
在网上&＃xff0c;多了一种方法。
如果一个数 不是6的倍数相邻的数&＃xff0c;肯定不是质数。 不能反推
public class LeetCode263 {public static void main(String[] args) {System.out.println(isUgly(50));}public static boolean isPrime(int n){if (n&＃61;&＃61;1||n&＃61;&＃61;2||n&＃61;&＃61;3||n&＃61;&＃61;5)return true;if(!(n%6&＃61;&＃61;1||n%6&＃61;&＃61;5)){return false;}int temp &＃61; (int)Math.sqrt(n);//必须是&＃61;&＃xff0c;不然25&＃xff0c;可以55 25for(int i&＃61;2;i<&＃61;temp;i&＃43;&＃43;){if (n%i&＃61;&＃61;0)return false;}return true;}public static boolean isUgly(int num) {if(num<&＃61;0)return false;if (num&＃61;&＃61;1||num&＃61;&＃61;2||num&＃61;&＃61;3||num&＃61;&＃61;5)return true;boolean result &＃61; false;if(num%2&＃61;&＃61;0){//如果是质数&＃xff0c;看是不是2、3、5int temp &＃61; num/2;if(isPrime(temp)){if(temp&＃61;&＃61;2||temp&＃61;&＃61;3||temp&＃61;&＃61;5){return true;}else {return false;}}else {//如果不是质数&＃xff0c;那看看这个数是不是丑数result &＃61; isUgly(num/2);}}if (result){return true;}else {if(num%3&＃61;&＃61;0){//如果是质数&＃xff0c;看是不是2、3、5int temp &＃61; num/3;if(isPrime(temp)){if(temp&＃61;&＃61;2||temp&＃61;&＃61;3||temp&＃61;&＃61;5){return true;}else {return false;}}else {result &＃61; isUgly(num/3);}}}if (result){return true;}else {if(num%5&＃61;&＃61;0){//如果是质数&＃xff0c;看是不是2、3、5int temp &＃61; num/5;if(isPrime(temp)){if(temp&＃61;&＃61;2||temp&＃61;&＃61;3||temp&＃61;&＃61;5){return true;}else {return false;}}else {result &＃61; isUgly(num/5);}}}return result;}}
太慢了
其实忘了一个条件&＃xff0c;这个商&＃xff0c;肯定也是2、3、5组合得来的。
所以丑数就是
2a x 3b x 5c
只有这里面&＃xff0c;没有别的质数就好了。但是2、3、5构成的&＃xff0c;怎会是质数呢&＃xff1f;
所以最后就是
public boolean isUgly(int num) {if(num<&＃61;0) return false;if(num&＃61;&＃61;1) return true;while(num%2&＃61;&＃61;0)num/&＃61;2;while(num%3&＃61;&＃61;0)num/&＃61;3;while(num%5&＃61;&＃61;0)num/&＃61;5;return (num&＃61;&＃61;1)?true:false; }
京公网安备 11010802041100号