Javaプログラムの実行時間を短縮

Question

プロジェクトオイラーの2番目の問題について、「Project Euler＃3：最大の素因数」の問題について、以下のプログラムを書いた。提供された入力。

import java.util.Scanner; 
public class euler_2 { 
    public static boolean isPrime(int n) { 
     if (n % 2 == 0) return false; 
     for (int i = 3; i * i <= n; i += 2) { 
      if (n % i == 0) 
       return false; 
     } 
     return true; 
    } 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int a = sc.nextInt(); 
     for (int i = 0; i < a; i++) { 
      int b = sc.nextInt(); 
      for (int j = b; j >= 1; j--) { 
       boolean aa = isPrime(j); 
       if (aa == true && b % j == 0) { 
        b = j; 
        break; 
       } 
      } 
      System.out.println(b); 
     } 
    } 
} 

プログラムをより高速に実行するために、どのような変更を加えることができますか？この問題のより良いアルゴリズムは何でしょうか？

Answer 1

問題は、すべての数Nのために、あなたはそれが素数であると、それはNの除数であるかどうかそれ以降か小さいかNに等しい各番号を試してみることです参照してください。

明白な改善は、最初に除数であるかどうかを確認し、次にそれが素数であるかどうかを確認することです。しかし、おそらくこれはあまり役に立たないでしょう。

代わりにできるのは、番号の除数であるかどうかをチェックすることです。除数の場合は、除算します。 sqrt(N)までこれを続けます。

私は長い間javaを使って何もしていませんが、ここでGoの実装があります。これはJavaの人がJavaに変換できる可能性が最も高いからです。

func biggestPrime(n uint64) uint64 { 
    p, i := uint64(1), uint64(0) 
    for i = 2; i < uint64(math.Sqrt(float64(n))) + uint64(1); i++ { 
     for n % i == 0 { 
      n /= i 
      p = i 
     } 
    } 
    if n > 1 { 
     p = n 
    } 
    return p 
} 

私のアルゴリズムを使用すると、最大の素数を見つけるためにO（sqrt（N））が必要になります。あなたの場合はO(N * sqrt(N))

Answer 2

番号を2つの要因に分解しようとします。今まで発見された最大の要因について、それが因数分解できないものを見つけるまで繰り返す - それが最大の素因です。

数字を因数分解しようとするかもしれない多くの方法がありますが、それらはintだけなので、Fermatの方法または試算（おそらくはsqrt（N）から降ります）がおそらく行います。あなたのアプローチとhttp://mathworld.wolfram.com/FermatsFactorizationMethod.html