0

ルールに従わなかったことに怒りを覚える前に、検索機能を利用して、この正確な問題に複数のスレッドがあることを確認しました。しかし、私の特定の質問には誰も答えませんでした。

オイラー問題 #3 に取り組んでいます。この問題では、最大の素因数 600851475143 を見つける必要があります。問題を解決するのに助けは必要ありません。私はそれを解決するためのブルートフォース法を作成しました(もっと良いかもしれません)。

プログラムは、小さい数字 (7 桁以下) で行ったすべてのテストで正しく返されます。ただし、長い入力として 600851475143 を入力すると、プログラムから返されることはありません。私の番号は単に大きすぎて入力できませんか? これが起こる原因は何ですか?当初は long ではなく int タグを使用していたためだと思っていましたが、それらを変更しても結果は変わりませんでした。

これは単純なことで、見逃していると確信していますが、何が起こっているのか非常に興味があります。前もって感謝します :)

//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

long変数は、目的の値を簡単にそれに合わせることができます

long: long データ型は、64 ビットの符号付き 2 の補数の整数です。最小値は -9,223,372,036,854,775,808 で、最大値は 9,223,372,036,854,775,807 (包括的) です。int によって提供される値よりも広い範囲の値が必要な場合は、このデータ型を使用します。

問題は、アルゴリズムが効率的でないことです。すでに述べたように、エラトステネスのふるいを使用してください。

于 2013-05-21T01:07:50.630 に答える
0

数値が素数かどうかを確認するには、エラトステネスのふるいisPrimeを使用します。単純な方法に比べてはるかに高速に実行されます。このフレーズのため、実装のヒントは提供しません: I don't need help solve the problem .

また、あなたが見逃した他のヒントがあるかもしれません。問題文を確認することをお勧めします。

最大の素因数は何ですか

于 2013-05-21T01:02:25.447 に答える