class eulerThree {
public static void main(String[] args) {
double x = 600851475143d;
for (double z = 2; z*z <= x; z++) {
if (x%z == 0) {
System.out.println(z + "PRIME FACTOR");
}
}
}
}
输出为:
71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0
所以,我假设486847是x的最大素数因子,但欧拉项目却不这么认为。我的代码和数学都没有问题,所以我很困惑。有什么我看不见的吗?
9条答案
按热度按时间xkftehaa1#
两件事:
不要使用
double
,数字越大,精度越低。相反,你可以使用BigInteger
存储任意大的整数,或者在本例中是一个简单的long
就够了。你需要在找到素数因子后除以它,否则你会找到所有的因子而不仅仅是素数因子。像这样:
dgenwo3n2#
由于素数no的工作原理是:大于1的整数要么是素数,要么可以写成素数的唯一积,这样我们就可以方便地使用上面的程序。在这个程序中,我们将长no除以,求出它的素数因子
62lalag43#
这是为了查看数据类型限制内任何数字中的最大素数因子。
bkhjykvo4#
看节目。你就会明白算法。这很简单,也很快。并返回正确答案6857。
vshtjzan5#
首先,使用biginteger或long而不是double。double是不精确的,而且当你遇到以后的问题时,它根本就不正确。
第二,你打印的是因素,而不是主要因素。
这将适用于您的情况:
此外,projecteuler还提供了示例输入和输出。使用它,因为您的代码不会输出与问题中给出的示例匹配的值。
3b6akqbq6#
vcudknz37#
ffdz8vbo8#
首先,你必须使用精确的算术平均数。其他人建议使用
BigInteger
. 你能做到的。对我来说,这感觉有点像作弊(这对以后处理更大整数的问题更重要),所以更有趣的方法(imho)是自己编写必要的任意精度运算。其次,600851475143规模偏小,做多精准
long
,速度会快得多。第三,你的循环没有正确地检查主要因素。你只是在查奇数。这是一个简单(不完整)的解决方案:
检查某个东西是否是prime有不同的实现级别。最天真的:
当然,这会做各种不必要的检查。因为你已经决定了你只需要检查数字到
sqrt(n)
您可以消除偶数(2除外):但你也可以做得更好。另一个优化是,您只需要在该范围内按素数检查一个数。63的主因子是3和7。如果一个数字不能被3或7整除,那么根据定义它就不能被63整除。
所以你要做的是建立一个
Set<Long>
或素数,直到平方等于或高于目标数。然后检查这一系列的数字是否可以被整除到目标中。eulz3vhy9#
double
对于大值来说本质上是不准确的,不应该用于这些类型的数字运算。正确使用的类是BigInteger
,允许精确表示任意大的整数值。有关浮点数据类型是什么和不是什么的描述,请参阅这篇wikipedia文章。