0

質問：

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

これは非常に簡単だと思いましたが、ファイルの実行には非常に長い時間がかかりました.しばらくの間続いていて、私が持っている最大数は716151937です.

これが私のコードです。待つだけですか、それともコードにエラーがありますか?

        //User made class
public class Three
{   
        public static boolean checkPrime(long p)
        {
            long i;
            boolean prime = false;
        for(i = 2;i<p/2;i++)
        {
            if(p%i==0)
            {
                prime = true;
                break;
            }
        }
    return prime;
    }

}

    //Note: This is a separate file
public class ThreeMain
{
    public static void main(String[] args)
        {
            long comp = 600851475143L;
            boolean prime;
            long i;
            for(i=2;i<comp/2;i++)
            {
                if(comp%i==0)
                {
                    prime = Three.checkPrime(i);
                    if(prime==true)
                    {
                        System.out.println(i);
                    }
                }
            }
        }       
}
4

5 に答える 5

1

あなたは正しい方向に向かっていますが、あなたは行く必要のある場所を通り過ぎて、途中でいくつかの間違いを犯しています。現在、素数を検証するために必要な値よりもはるかに高い値をチェックしています（特に素数>> 2）。あなたの行：for(i = 2;i<p/2;i++)可能性がありますfor(i = 2;i*i <= p;i++)（素数か合成数かを判断するには、数値の平方根までチェックするだけで済みます）。

素数をチェックする関数は、実際には素数ではなくコンポジットに対してtrueを返します。あなたはコードです：

    if ((p%i==0) {
        prime = true;
        break; }

する必要があります

    if ((p%i==0) {
        prime = false;
        break; }

あなたの主な方法では、実際にはまったく必要ありませんboolean prime。質問の文脈から、3つ以上の素因数があると想定できます。つまり、compをより小さく、より管理しやすい数に減らすために必要な最大の素因数は、compの立方根です。したがって、あなたの行for(i=2;i<comp/2;i++)はである可能性がありますfor(i=2;i*i*i<comp;i++)。i 除算するかどうかを継続的にチェックしてから素数であるcompかどうかをチェックする代わりに、除算がなくなるまで除算することでサイズを減らすことができます（の累乗をチェックするため）。の小さい値から始めているので、毎回減らすと、除算される合成数を取得することはありません。あなたが減らしたときicompicompiiicompicomp1にすると、電流iが最大の素因数となり、問題に対する答えになります。

また、あなたはラインです：

    prime = Three.checkPrime(i);
    if(prime==true)

次のように減らすことができます：

if (Three.checkPrime(i));

Three.checkPrime（）はブール値を返し、最終的にはブール値として評価されるためです。

于 2012-12-06T05:59:55.030 に答える
0

sqrt(2)ループする代わりに、ループするだけn/2で多くの時間を節約できます。

于 2012-11-06T05:23:49.787 に答える
0

あなたのアルゴリズムは遅いです。試行除算によって整数を因数分解する標準的な方法は次のとおりです。

define factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n /= f
        else
            f = f + 1
    output n

整数を素因数分解するより良い方法があります。それらのいくつかについては、私のブログのエッセイで読むことができます。しかし、このアルゴリズムはプロジェクト オイラー #3 には十分であり、ほとんどの現代言語で 1 秒以内に答えを返します。

于 2012-11-06T16:19:06.397 に答える
0

ここでは、この問題を解決するために 2 つの異なるロジックを記述しています。私はそれがより速く動作することを確信しています

最初のものは

import java.util.ArrayList;
import java.util.List;

public class Problem3 {
public void hfactor(long num)
 {
  List<Long> ob =new ArrayList<Long>();
 long working =num;
  long current =2;
  while(working !=1)
   {boolean isprime = true;
    for(Long prime :ob)
    {
      if(current%prime == 0)
       { isprime =false;
         break;   
       }
    }
    if(isprime)
    {ob.add(current);
       if(working%current ==0)
       {
       working /=current;
        }
     } 

  current++;    
    }
    System.out.println(ob.get(ob.size()-1));
   }    


 public static void main(String[] args) {
  Problem3 ob1 =new Problem3();
  ob1.hfactor(13195);
  }
  }

2番目は

public static void main(String[] args) {
    List <Long> ob = new ArrayList<Long>(); 
    List<Long> ob1 = new ArrayList<Long>();

    long num =13195;
    for(int i = 2; i<num; i++)
      {
       if (num%i ==0)
         ob.add((long) i);  
      }

    for (int i =0; i<ob.size(); i++)
        for(int j =2; j<ob.get(i); j++)
            {
             if (ob.get(i)%j ==0)
                {
                 ob.set(i, (long) 0);
                    }
             }
           for(int i =0; i<ob.size(); i++){
              if(ob.get(i)!=0)
              {
                 ob1.add(ob.get(i)); 
              } 


             }

        System.out.println(ob1.get(ob1.size()-1));



    }}
于 2013-03-09T16:43:06.430 に答える
0

自分の数の約数がわかったら、それを割って残りの数を小さくすることができます。

if (prime)
{
    System.out.println(i);

    // The factor may occur multiple times, so we need a loop.                
    do {
        comp /= i;
    } while (comp % i == 0);
}

これを行うと、すべての小さな素数が既に除算されているため、常にi除算が素数compでなければならないことが保証されるため、素数チェックを削除できます。i

for (i = 2; i < comp/2; i++)
{
    if (comp % i == 0)
    {
        System.out.println(i);

        do {
            comp /= i;
        } while (comp % i == 0);
    }
}

最後に、平方根よりも大きい因数には平方根より小さい因数が伴う必要があるため、i平方根までチェックするだけで済みます。comp(つまりi*j == comp、iまたは のいずれかがの平方根でjなければならない場合)。<=comp

適用できるトリックは他にもいくつかありますが、この問題にはこれで十分です。

于 2012-11-06T05:44:10.167 に答える