0

在我因为不遵守规则而受到抨击之前,我确实使用了搜索功能,并看到这个问题有多个线程。但是,他们都没有回答我的具体问题。

我正在研究欧拉问题#3,我需要找到 600851475143 的最高素数。我不需要帮助来解决问题。我已经提出了一种蛮力方法(我知道可能会更好)来解决它。

对于我使用较小数字(7 位数及以下)所做的所有测试,该程序都会正确返回。但是,当我输入 600851475143 作为长输入时,我的程序永远不会给我返回。我的号码是否太大而无法输入?什么可能导致这种情况发生?我最初认为这是因为我使用的是 int 标签而不是 long,但更改这些标签并没有改变我的结果。

我确信这很简单,我很想念它,但我很好奇发生了什么。先感谢您 :)

//Euler 3: Largest Prime Factor
import java.io.*;
import java.util.Scanner;
import java.lang.Math;


public class Euler3 
{
    public static void main(String[] args)
    {
        Scanner scn = new Scanner(System.in);

        System.out.println("Enter a number!");
        // Create scanner
        long numberInput=scn.nextLong();
        //Can't have a factor higher than it's square root
        double limit=Math.floor(Math.sqrt(numberInput));
        // System.out.println(limit);

        //Start testing from the highest number possible
        for(long i=(numberInput-1);i>0; i--)
        {
            if(numberInput%i==0) 
                System.out.println(i+" is prime: "+isPrime(i));

        }

    } //End Main


    public static boolean isPrime(long n) 
    {
        //check if n is a multiple of 2
        if (n%2==0) return false;
        //if not, then just check the odds
        for(int i=3;i*i<=n;i+=2)
        {
            if(n%i==0)
                return false;
        }
        return true;
    }
}   
4

3 回答 3

0

The problem is not in the isPrime method but in the loop you use to call it. You count down from your number n with increments of 1, and you call isPrime only for divisors of n: it will take n/2 steps before you get to the first potential divisor of n - so, in the order of 10^12 steps for your example n.

于 2013-05-29T04:43:58.693 回答
0

要验证一个数字是否为素数,请使用Eratosthenes 筛,isPrime与您的幼稚方法相比,它会运行得更快。由于这句话,我不会提供任何实现提示:我不需要帮助解决问题

此外,您可能错过了其他提示。我建议您查看问题陈述:

最大的质因数是多少

于 2013-05-21T01:02:25.447 回答
0

long变量可以轻松地将您想要的值放入其中

long:long 数据类型是一个 64 位有符号二进制补码整数。它的最小值为-9,223,372,036,854,775,808,最大值为9,223,372,036,854,775,807(含)。当您需要比 int 提供的值范围更广的值时,请使用此数据类型。

问题是您的算法不是一种有效的算法。如前所述,使用埃拉托色尼筛

于 2013-05-21T01:07:50.630 回答