project euler#3 java解决方案问题

vbkedwbf  于 2021-07-05  发布在  Java
关注(0)|答案(9)|浏览(248)
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的最大素数因子,但欧拉项目却不这么认为。我的代码和数学都没有问题,所以我很困惑。有什么我看不见的吗?

xkftehaa

xkftehaa1#

两件事:
不要使用 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
}
dgenwo3n

dgenwo3n2#

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);
}
}

由于素数no的工作原理是:大于1的整数要么是素数,要么可以写成素数的唯一积,这样我们就可以方便地使用上面的程序。在这个程序中,我们将长no除以,求出它的素数因子

62lalag4

62lalag43#

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);
                               }
                           }
                     }
                  }
            }
          }

这是为了查看数据类型限制内任何数字中的最大素数因子。

bkhjykvo

bkhjykvo4#

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));
    }
}

看节目。你就会明白算法。这很简单,也很快。并返回正确答案6857。

vshtjzan

vshtjzan5#

首先,使用biginteger或long而不是double。double是不精确的,而且当你遇到以后的问题时,它根本就不正确。
第二,你打印的是因素,而不是主要因素。
这将适用于您的情况:

for (double z = 2; z <= x; z++) {
        if (x%z == 0) {
                    while( x%z == 0)
                        x = x/z
                System.out.println(z + "PRIME FACTOR");
        }
}

此外,projecteuler还提供了示例输入和输出。使用它,因为您的代码不会输出与问题中给出的示例匹配的值。

3b6akqbq

3b6akqbq6#

long tNum=600851475143L;

ArrayList<Integer> primeNum=new ArrayList();
System.out.println(10086647/1471);
for(int i=2;i<=tNum;i++) {
    if(tNum%i==0) {
        primeNum.add(i);
        tNum=tNum/i;    
    }
}

System.out.println(primeNum);
vcudknz3

vcudknz37#

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();
    }
}
ffdz8vbo

ffdz8vbo8#

首先,你必须使用精确的算术平均数。其他人建议使用 BigInteger . 你能做到的。对我来说,这感觉有点像作弊(这对以后处理更大整数的问题更重要),所以更有趣的方法(imho)是自己编写必要的任意精度运算。
其次,600851475143规模偏小,做多精准 long ,速度会快得多。
第三,你的循环没有正确地检查主要因素。你只是在查奇数。这是一个简单(不完整)的解决方案:

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
}

检查某个东西是否是prime有不同的实现级别。最天真的:

public boolean isPrime(long num) {
  for (long i=2; i<=num; i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

当然,这会做各种不必要的检查。因为你已经决定了你只需要检查数字到 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;
}

但你也可以做得更好。另一个优化是,您只需要在该范围内按素数检查一个数。63的主因子是3和7。如果一个数字不能被3或7整除,那么根据定义它就不能被63整除。
所以你要做的是建立一个 Set<Long> 或素数,直到平方等于或高于目标数。然后检查这一系列的数字是否可以被整除到目标中。

eulz3vhy

eulz3vhy9#

double 对于大值来说本质上是不准确的,不应该用于这些类型的数字运算。正确使用的类是 BigInteger ,允许精确表示任意大的整数值。有关浮点数据类型是什么和不是什么的描述,请参阅这篇wikipedia文章。

相关问题