8

私は最近、私の学校で小さなJavaプログラミングコンテストに参加しました。私のパートナーと私は最初の純粋なoopクラスを終えたばかりで、ほとんどの質問は私たちのリーグから外れていたので、これに落ち着きました（そして私は多少言い換えています）：「入力整数nが与えられた場合、プライムである次のintを返しますその逆も素数です。たとえば、n = 18の場合、31と13は両方とも素数であるため、プログラムは31"を出力する必要があります。.classファイルには、1〜2,000,000,000のすべての可能な数値のテストケースが渡され、有効と見なされるには10秒以内に正解を返す必要がありました。

解決策を見つけましたが、テストケースが大きい場合は、10秒以上かかります。ループの範囲をn、.. 2,000,000,000から下に移動する方法があると確信しています。これは、nが小さい場合にループする必要がある可能性が低いためですが、どちらの方法でも、数値が小さい場合はループを解除します。両方の条件下で素数が見つかります。最初は2、.. nからループしていましたが、それがどれほど大きくても、nの平方根にのみループするという規則を思い出しました。私のプログラムをより効率的にする方法について何か提案はありますか？アルゴリズムの複雑さの分析を扱うクラスはありませんでした。これが私たちの試みです。

public class P3
{

   public static void main(String[] args){

    long loop = 2000000000;
    long n = Integer.parseInt(args[0]);
    for(long i = n; i<loop; i++)
    {
      String s = i +"";
      String r = "";
      for(int j = s.length()-1; j>=0; j--)
        r = r + s.charAt(j);
      if(prime(i) && prime(Long.parseLong(r)))
      {
          System.out.println(i);
          break;
      }
    }
    System.out.println("#");
  }

  public static boolean prime(long p){


for(int i = 2; i<(int)Math.sqrt(p); i++)
    {
      if(p%i==0)
        return false;
    }
    return true;
  }
}

コードのフォーマットを間違えた場合は申し訳ありませんが、ここに投稿するのはこれが初めてです。また、出力には各行の後に「＃」が必要でした。これは、ループの後の行が何であるかを示しています。皆さんが提供してくれた助けに感謝します!!!

4

11 に答える 11

17

まず、エラトステネスのふるいのようなものを使用して、2,000,000,000までのすべての素数を事前に計算する必要があります。各数値が素数であるかどうかをビット配列に格納できます。

これは非常に高速であり、個々の数値の素数性をチェックするのは簡単な検索です。

テストケースごとにプログラムの新しいインスタンスを実行する必要があるためにこれを実行できない場合は、ミラーラビンのような高速の素数テストアルゴリズムを使用してください。

于 2010-05-05T23:51:59.880 に答える
7

あなたの素数チェックは非常に非効率的です。実際、すでにチェックされている数値の倍数を再チェックする必要はありません。したがって、％2をチェックする場合、％4をチェックする必要はありません。

数値が素数であるかどうかを確認するには、チェックする数値の平方根に達するまで、既知のすべての素数で除算するだけです。これを行うと、分割数が大幅に減少します。アプリに2 ..〜44721の素数のリストがある場合（たとえば、準備ステップとして計算）、2000000000までのすべての数値を非常にすばやく確認できます。

また、最初に2つの順列のうち小さい方をチェックする必要があります（たとえば、サンプルでは最初に13をチェックし、次に31をチェックします）。

編集：

これが私がC＃ですばやくまとめたサンプルです（Javaで実行するには、構文を少し変更する必要がありますが、C＃コンパイラが手元にありました）。

public static long reverse(long value) {
    long result = 0;
    while (value > 0) {
        result = result*10+(value%10);
        value /= 10;
    }
    return result;
}

public static long[] knownPrimes = new long[1000000];
public static int knownPrimeCount = 0;

public static bool isPrime(long value) {
    // we loop through all already known primes and try to divide by those (sieve sort of)
    for (int primeIndex = 0; primeIndex < knownPrimeCount; primeIndex++) {
        long primeToCheck = knownPrimes[primeIndex];
        if (value % knownPrimes[primeIndex] == 0) {
            // can be divided by the given prime -> not a prime
            return false;
        }
        if ((primeToCheck * primeToCheck) > value) {
            // square exceeds the value -> is a prime, no more checks needed
            return true;
        }
    }
    // if we come here, we've run out of primes to check against, and therefore we should indicate this as error
    throw new ArgumentException(string.Format("{0} is too large to be checked against known primes", value), "value");
}

public static void Main(String[] args){
    long loop = 2000000000;
    long n =    1999990000;

    // first we initialize all the primes we may be needing for the final computation
    knownPrimes[knownPrimeCount++] = 2;
    for (long i = 3; true; i++) {
        if (isPrime(i)) {
            // store the new prime
            knownPrimes[knownPrimeCount++] = i;
            if ((i * i) > loop) {
                break; // we have all the primes we need now
            }
        }
    }

    // now we try to find matches
    for (long i = n; i <= loop; i++) {
        long reversed = reverse(i);
        if ((reversed <= i) && isPrime(reversed) && isPrime(i)) {
            Console.WriteLine("{0} <-> {1}", i, reversed);
        }
    }
    Console.WriteLine("#");
    Console.ReadKey(true);
}

私のコンピューターでは、与えられloopたnソースで結果が瞬時に表示されます。

于 2010-05-05T23:53:39.223 に答える
5

を使用するBigInteger.isProbablePrime(certainty)と、BigInteger.nextProbablePrime()非常に効率的にチェックする必要があるケースの数を大幅に減らすことができます

于 2010-05-05T23:58:37.320 に答える
4

1ずつインクリメントしているように見えますが、2ずつインクリメントする必要があります。偶数は素数ではなく2です。

于 2010-05-05T23:51:35.433 に答える
0

ここでの大きな非効率性は、主要なテスト方法primeです。まったく同じ数をテストする必要がある回数を考えて、繰り返される計算の一部を回避するために、メモリ構造をどのように利用できるかに集中してください。

于 2010-05-05T23:53:23.287 に答える
0

私はこれまでこれを行ったことがありませんが、ここで頭に浮かぶことがいくつかあります。

平方根が整数の場合、その数は素数ではありません

数が0、2、4、5、6、または8で終わる場合、素数ではありません/2自体を除く

桁の合計が3で割り切れる場合は、数値を3で割ることができ、合計が9の場合は9で割ることができます。

このことをテストすることが役立つかどうかはわかりません。とにかく計算する必要があり、すでに実行できるため、少なくともsquareRootのテストが役立つはずです。

もちろん、ミラー-ラビン素数性テストhttp://en.wikipedia.org/wiki/Miller-Rabin_primality_testのようなことを行うと、効率が大幅に向上します。実際のテストは、特定のケースがない場合にのみ実行する必要があります。

于 2010-05-05T23:59:46.133 に答える
0

Miller-Rabin検定を使用するよりもさらに高速です。これは確率的テストであるため、ある程度の誤差があります。ただし、テストは複数回実行されるため、必要に応じてエラーを小さくすることができます (多くの場合、商用アプリケーションでは 50 で十分です)。

Java ではありませんが、私が作成した Python での簡単な実装を次に示します。

于 2010-05-10T00:27:01.697 に答える
0

@Davidは数値の平方根を取得し、平方根が偶数を除去するまでループし、割り切れないかどうかを確認します

于 2010-09-08T11:14:01.577 に答える
0

最も簡単なオプションは、既存の大きな整数ライブラリを使用することです。バグはなく、すべてのサポート機能を提供します。

独自の実装 (つまり、課題用) を作成している場合は、自分が何をしているのかを理解できるように、本の疑似コード アルゴリズムから作業することをお勧めします。

そうは言っても、最も簡単な方法の 1 つは、Jacobi と Legendre を使用して同等性を比較することです。RSA 暗号化の課題を提出しました。これは私が単精度で行ったことですが、アルゴリズムは一般的で、多倍精度の整数でも機能します。

typedef uint64_t BigIntT;
typedef int64_t SBigIntT;

// This function calculations the power of b^e mod phi
// As long as 
//      b*b is smaller than max(BigIntT) 
//      b*phi is smaller than max(BigIntT)
// we will not have overflow.
BigIntT calculatePower (BigIntT b, BigIntT e, BigIntT m) {
    BigIntT result = 1;

    while (e != 0) {
        if (e & 1) {
            result = (result * b) % m;
        }

        e = e >> 1;
        b = (b * b) % m;
    }

    return result;
}

// This function implements simple jacobi test.
// We can expect compiler to perform tail-call optimisation.
SBigIntT jacobi (SBigIntT a, SBigIntT b) {
    if (a == 0 || a == 1) {
        return a;
    } else if (a % 2 == 0) {
        if (((b*b - 1) / 8) % 2 == 0) {
            return jacobi(a/2, b);
        } else {
            return -jacobi(a/2, b);
        }
    } else if ((((a-1) * (b-1)) / 4) % 2 == 0) {
        return jacobi(b % a, a);
    } else {
        return -jacobi(b % a, a);
    }
}

// This function implements : http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test
bool testPrime (BigIntT p) {
    int tests = 10;

    if (p == 2) {
        return true;
    }

    while (tests-- > 0) {
        BigIntT a = generateRandomNumber(2, p);

        if (greatestCommonDivisor(a, p) == 1) {
            BigIntT l = calculatePower(a, (p-1)/2, p);
            SBigIntT j = jacobi(a, p);

            // j % p == l
            if ((j == -1) && (l == p-1) || (j == l)) {
                // So far so good...
            } else {
                // p is composite
                return false;
            }
        } else {
            // p is composite
            return false;
        }
    }

    return true;
}

数が多い場合でもパフォーマンスは非常に優れています。

于 2010-09-08T10:45:39.737 に答える
0

@outis...私はあなたが言っていることを理解しています。それは私が言わなければならないきちんとした小さなトリックです。有難うございます。

@Graham ...また、あなたが言及したテストに関する記事を読みました。なぜなら、あなたが作成したコメントからその要点を理解したと思いますが、Pythonは常に私にはギリシャ語のように見えるからです。誰もが簡単な言語の 1 つだと言っていることは知っていますが、なんらかの理由で Java と C++ は常に私には読みやすいように見えます。とにかく、それはそれを行うためのはるかに良い方法だったでしょう. このボードから多くのことを学んだヒントをくれた皆さんに、改めて感謝します。秋にデータ構造とアルゴリズムのクラスを受講することはできません!!!

于 2010-05-11T04:02:11.900 に答える
0

実行できるもう 1 つの速度改善mainは、いくつかの合成数を事前にフィルター処理するようにループを変更し、いくつかの反復を一連のテストに展開することです。最も簡単な方法は、ループの外で 2 をテストしてから、奇数をテストすることです ( 2*i+1)。もう少し複雑なのは、2、3、次に をテストすること6*i ± 1です。このアプローチを拡張し続け、最初の n 個の素数をテストしてから、oven をループします。ここで、p n #は原始素数 (最初の n 個の素数の積) であり、j は p n #より小さく互いに素な正の整数です。pn# * i+j

primeメソッドを高速化するには、高速な確率的素数テストから開始し、確率的テストで判断できない場合にのみ、より遅い決定論的テストを使用してテストすることができます。

于 2010-05-06T02:28:56.893 に答える