判断一个自然数是否是某个数的平方。
51CTO上的参考答案如下 写道
假设待判断的数字是 N。
方法1:
遍历从1到N的数字,求取平方并和N进行比较。
如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。
复杂度为O(n^0.5)。
方法2:
使用二分查找法,对1到N之间的数字进行判断。
复杂度为O(log n)。
方法3:
由于
(n+1)^2
=n^2 + 2n + 1,
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到这些项构成了等差数列(每项之间相差2)。
所以我们可以比较 N-1, N - 1 - 3, N - 1 - 3 - 5 ... 和0的关系。
如果大于0,则继续减;如果等于0,则成功退出;如果小于 0,则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些。
方法3不是很看得懂。。。
我的想法 写道
public static boolean getResult(int number) {
int in = number;
int num = 0;
for (int i = 2; i <= in;) {
if (in % i == 0) {
in = in / i;
num++;
if (in == 1 && num % 2 == 0) {
return true;
}
} else {
if (num % 2 != 0) {
return false;
}
i++;
}
}
return false;
}
不知道有木有更好的算法
分享到:
相关推荐
对应每组输入,如果查找到x,则每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开;如果没有查找到x,则每行输出NO. Sample Input 8 100 2 4 2 4 5 100 2 100 8 3 2 4 2 4 5 100 2 100 ...
C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c
本程序用CUDA编程在linux环境下实现了判断一个自然数是否为素数的操作。
给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n); (2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3) 按此规则进行处理,直到不能再添加自然数为止。 ...
当你输入一个数据时,系统会自动判断它是否是一个素数,很好用的,实用,简单。欢迎下载,并且是免费的。
c++ 实现一个自然数表示成几个自然数的和,输出所有自然数和的表示方式
java代码-例子3-13 输入一个自然数,判断该数是否为素数
属于课程实例,输出一个自然数的各项因子。
C语言程序设计-计算从1开始到n的自然数中偶数的平方的和,n由键盘输入,并在main()函数中输出。(n是偶数).c
编写一个程序。要求将一个自然数拆分成任意个自然数相加,要求这几个数的乘积是最大的 自然数n拆分成m个自然数,要求这几个数的乘积是最大的,必为n/m及其临近数.
最大公约数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
问题描述: 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。...接下来的n 行中,每行有一个自然数。 结果输出: 程序运行结束时,输出有2 行,第1 行给出众数,第2 行是重数。
python判断是否是回文数,简单明了易于进一步学习和思考。
python回文数判断。设n是一任意自然数,如果n的各位数字反向排列所得自然数与n相等,则n被称为回文数。从键盘输入一个5位数字,判断这个数字是不是回文数
输入一个自然数n,求1~n之间的所有自然数之和。
设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数。例如,若n=1234321,则称n为一回文数;但若n=1234567,则n不是回文数。
一个自然数幂和公式的推导,陆多俊,,本文从对递推关系求解的角度,推导出自然数幂和的组合数表达形式。为计算机求解幂和问题提供了方法和依据。
写一个程序,对于给定的一个自然数N(1),和M个互不相同的十进制数字X1, X2,…,XM (M>=1), 找出N的一个最小的正倍数,使得该倍数中仅包含数字X1,X2,…,XM。 【输入形式】 输入文件为当前目录下的...
输入一个整数判断其是否是回文数……可以直接在vc6.0平台上 直接运行通过,例如输入 121 ,则输出,恭喜您,您输入的是回文数……呵呵,见笑了,学习学习……
判断一个数是否为素数 判断一个数是否为素数可以通过检查它是否只能被1和它本身整除来实现。以下是一个简单的 Python 函数来判断一个数是否为素数: ```python def is_prime(n): if n return False if n ...