Project Euler #3 Java 解决方案问题
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1656197/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Project Euler #3 Java Solution Problem
提问by Catharsis
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");
}
}
}
}
and the output is:
输出是：
71.0
839.0
1471.0
6857.0
59569.0
104441.0
486847.0
So, I assume 486847 is the largest prime factor of x, but project euler says otherwise. I don't see a problem in my code or my math, so I'm pretty confused. Can you see anything I can't?
所以，我假设 486847 是 x 的最大质因数，但项目 euler 另有说法。我在我的代码或数学中没有看到问题，所以我很困惑。你能看到我看不到的东西吗？
回答by cletus
Firstly, you have to use an accurate arithmetic means. Others have suggested using BigInteger. You can do this. To me, it feels a bit like cheating (this will be more important for later problems that deal with much larger integers) so the more fun way (imho) is to write the necessary arbitrary precision operations yourself.
首先，您必须使用准确的算术方法。其他人建议使用BigInteger. 你可以这样做。对我来说，这感觉有点像作弊（这对于以后处理更大整数的问题更重要），所以更有趣的方法（恕我直言）是自己编写必要的任意精度操作。
Second, 600851475143 is small enough to be done accurate with a long, which will be much faster.
其次， 600851475143 足够小，可以用 a 准确完成long，这会快得多。
Third, your loop isn't correctly checking for prime factors. You're just checking odd numbers. This is a barebones (incomplete) solution:
第三，您的循环没有正确检查主要因素。你只是在检查奇数。这是一个准系统（不完整）解决方案：
long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
// first check i is prime
// if i is prime check if it is a factor of num
}
Checking if something is prime has differing levels of implementation. The most naive:
检查某些东西是否是主要的具有不同的实现级别。最天真：
public boolean isPrime(long num) {
for (long i=2; i<=num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
Of course that does all sorts of unnecessary checking. As you've already determined you only need to check numbers up to sqrt(n)and you can eliminate even numbers (other than 2):
当然，这会进行各种不必要的检查。正如您已经确定的那样，您只需要检查数字sqrt(n)，您就可以消除偶数（2 除外）：
public boolean isPrime(long num) {
if (num & 1 == 0) {
return false; // checks divisibility by 2
}
for (long i=3; i*i<=num; i+=2) {
if (num % i == 0) {
return false;
}
}
return true;
}
But you can do better than this as well. Another optimization is that you only need to check a number by prime numberswithin that range. The prime factors of 63 are 3 and 7. If a number isn't divisible by 3 or 7 then it by definition won't be divisible by 63.
但你也可以做得比这更好。另一个优化是您只需要通过该范围内的素数来检查数字。63 的质因数是 3 和 7。如果一个数不能被 3 或 7 整除，那么根据定义，它也不能被 63 整除。
So what you want to do is build up probably a Set<Long>or prime numbers until the square is equal to or higher than your target number. Then just check this series of numbers for divisibility into the target.
所以你想要做的可能是建立一个Set<Long>或素数，直到平方等于或高于你的目标数。然后只需检查这一系列数字是否可整除为目标。
回答by Ramon
doubleis inherently inaccurate for large values and should neverbe used for these type of number operations. The right class to use is BigInteger, which allows arbitrarily large integral values to be represented precisely. See this wikipedia articlefor a description on what floating point data types are and are not.
double对于大值本质上是不准确的，永远不应该用于这些类型的数字运算。要使用的正确类是BigInteger，它允许精确表示任意大的整数值。有关浮点数据类型是什么和不是什么的描述，请参阅此维基百科文章。
回答by Reverend Gonzo
First, use BigInteger or long rather than double. Double isn't exact, and as you get to later problems, it won't be correct at all.
首先，使用 BigInteger 或 long 而不是 double。Double 并不准确，当您遇到以后的问题时，它根本就不正确。
Second, what you're printing is factors, not prime factors.
其次，您打印的是因素，而不是主要因素。
This will work in your case:
这将适用于您的情况：
for (double z = 2; z <= x; z++) {
if (x%z == 0) {
while( x%z == 0)
x = x/z
System.out.println(z + "PRIME FACTOR");
}
}
Also, Project Euler gives you sample input and output. Use that, since your code doesn't output values that match the example they give in the problem.
此外，Project Euler 为您提供示例输入和输出。使用它，因为您的代码不会输出与他们在问题中给出的示例相匹配的值。
回答by John Kugelman
Two things:
两件事情：
Don't use
double, the bigger the numbers the less precision it has. Instead you can useBigIntegerto store arbitrarily large integers, or in this case a simplelongwill suffice.You need to divide by the prime factor after you find it, otherwise you'll find all factors not just prime factors. Something like this:
if (x % z == 0) { System.out.println(z + "PRIME FACTOR"); x /= z; z -= 1; // Might be present multiple times, try it again }
不要使用
double，数字越大精度越低。相反，您可以使用BigInteger存储任意大的整数，或者在这种情况下，一个简单的long就足够了。找到后需要除以质因数，否则会找到所有因数而不仅仅是质因数。像这样的东西：
if (x % z == 0) { System.out.println(z + "PRIME FACTOR"); x /= z; z -= 1; // Might be present multiple times, try it again }
回答by Jedi Dula
public class Prime {
public static void main(String[] args) {
double out = 0;
double m = 600851475143d;
for (double n = 3; n < m; n += 2) {
while (m % n == 0) {
out = n;
m = m / n;
}
}
System.out.println("" + ((m == 1)?out:m));
}
}
See the program. And you'll understand the algorithm. This is very easy and very fast. And return the correct answer 6857.
看节目。你会理解算法。这非常容易且非常快。并返回正确答案 6857。
回答by Deepeshkumar
import java.util.Scanner;
class Primefactor
{
public static void main(String args[])
{
Scanner get=new Scanner(System.in);
System.out.println("Enter a number");
long number=get.nextLong();
int count=0;
long input=number;
for(long i=number;i>=1;number--)
{
for(long j=number;j>=1;j--)
{
if(i%j==0)
{
count++;
}
if(count==2)
{
if(input%j==0)
{
System.out.println(j);
}
}
}
}
}
}
This is to see largest primefactor of any number within the datatype limit.
这是为了查看数据类型限制内任何数字的最大素数。
回答by user3651256
public static void largestPrimeNo(long lim)
{
long newNum = lim;
long largestFact = 0;
int counter = 2;
while( counter * counter <= newNum )
{
if(newNum % counter == 0)
{
newNum = newNum / counter;
largestFact = counter;
}else{
counter++;
}
}
if(newNum > largestFact)
{
largestFact=newNum;
}
System.out.println(largestFact);
}
}
as Prime no is work on the principle that Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers.So we can easily use above program.In this program we divide the long no,and find its prime factor
因为质数的原理是任何大于 1 的整数要么是质数，要么可以写成质数的唯一乘积。所以我们可以很容易地使用上面的程序。在这个程序中，我们将长数除以找到它的主要因素
回答by Prasanka Samaraweera
package findlaragestprimefactor;
public class FindLaragestPrimeFactor{
boolean isPrime(long number) {
for (long divider = 2; divider <= number / 2; divider++) {
if (number % divider == 0) {
return false;
}
}
return true;
}
void calculateLargestPrimeFactor() {
long largestPrimeFactor = 0;
long x = 600851475143L;
for(long factor = 3 ; factor <= x/2 ; factor = factor + 2){
if(x%factor==0 & factor>largestPrimeFactor & isPrime(factor)){
largestPrimeFactor = factor;
}
}
System.out.println(largestPrimeFactor);
}
public static void main(String[] args) {
MyProject m = new MyProject();
m.calculateLargestPrimeFactor();
}
}
