-1

試行分割による素数性をテストするためのこのアルゴリズムに出くわしました このアルゴリズムを完全に理解しています

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

それはうまく動作します。しかし、その後、同じように機能するこの別のものに出くわしましたが、その背後にあるロジックを完全には理解していません.

static boolean isPrime(int N) {
    if (N < 2)
        return false;
    for (int i = 2; i * i<N; i++)
        if (N % i == 0)
            return false;
    return true;
}

のようにi *i < N振る舞うようi <= Math.sqrt(N)です。もしそうなら、なぜですか？

4

2 に答える 2

2

余談ですが、コードが遅すぎると思われる場合は、いくつかの調整でコードを高速化できます。

static boolean isPrime(int N) {
    if (N <= 1)
        return false;
    if (N % 2 == 0)
        return N == 2;
    for (int i = 3; i <= Math.sqrt(N); i += 2)
        if (N % i == 0)
            return false;
    return true;
}

このバージョンでは、負数と 2 で割り切れるかどうかの特別なテストを行い、それ以降は 3、5、7、... (「+= 2」に注意してください) の奇数で除算します。

于 2013-11-03T11:23:35.440 に答える