丑数(c语言)

题目描述

我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。输入一个数n，判断它是否是丑数。是丑数输出YES,不是丑数输出NO。

输入

输入n：
6

输出

输出：
YES

样例输入 

8

样例输出 

YES

提示

提示一、数据范围 1<=n<=9223372036854775807
提示二、除2 3 5 外的质数都不是丑数

 1.这个题目穷举可能会时间超限，刚开始是我也是没有思路的。然后后面我就想到了分解质因数这个事情。

2.跟分解质因数有点相似呢，我们从2开始，如果n能除断，我们把n变小，直到2除不尽，这样子的话，我们每次除的就一定是质数，不可能是合数，因为合数最终会分解成质数相乘。

3.然后我们就判断最后，n变成哪一个质数，如果这个质数大于等于5，那么它就不是丑数。如果是就是丑数。

献上代码：

#include<>
int slove(unsigned long long n)
{
	int i;
	for(i=2;i<n;)
	{
		if(n%i==0) n/=i;
		else i++;
	}
	return n<=5?1:0;
}
int main()
{
	unsigned long long n;
	scanf("%lld",&n);
	if(slove(n)==0) printf("NO\n");
	else printf("YES\n");
}