0

これは、オブジェクトのisPrime関数を表現する最もエレガントな方法ですか?BigInt

これが私が通常の整数のために持っているものです:

  def isPrimeForInt(n: Int): Boolean = {
    val ceiling = math.sqrt(n.toDouble).toInt
    (2 until ceiling) forall (x => n % x != 0)
  }

ここに私が BigInts のために持っているものがあります:

  def isPrimeForBigInt(n: BigInt): Boolean = {
    def ceiling: BigInt = {
      def f(a: BigInt): Stream[BigInt] = a #:: f(a+1)
      f(BigInt(1)).dropWhile(_.pow(2) < n)(0)
    }
    Range.BigInt(BigInt(2), ceiling , BigInt(1)) forall (x => n % x != 0)
  }
4

2 に答える 2

1

最初の例ではIntforを変更します。BigIntなんで書き直すの？

于 2013-01-25T20:44:00.817 に答える
1

BigInts の素数チェッカーは次のとおりです。

private static Boolean isSpsp(BigInteger n, BigInteger a)
{
    BigInteger two = BigInteger.valueOf(2);
    BigInteger n1 = n.subtract(BigInteger.ONE);
    BigInteger d = n1;
    int s = 0;

    while (d.mod(two).equals(BigInteger.ZERO))
    {
        d = d.divide(two);
        s += 1;
    }

    BigInteger t = a.modPow(d, n);

    if (t.equals(BigInteger.ONE) || t.equals(n1))
    {
        return true;
    }

    while (--s > 0)
    {
        t = t.multiply(t).mod(n);
        if (t.equals(n1))
        {
            return true;
        }
    }

    return false;
}

public static Boolean isPrime(BigInteger n)
{
    Random r = new Random();
    BigInteger two = BigInteger.valueOf(2);
    BigInteger n3 = n.subtract(BigInteger.valueOf(3));
    BigInteger a;
    int k = 25;

    if (n.compareTo(two) < 0)
    {
        return false;
    }

    if (n.mod(two).equals(BigInteger.ZERO))
    {
        return n.equals(two);
    }

    while (k > 0)
    {
        a = new BigInteger(n.bitLength(), r).add(two);
        while (a.compareTo(n) >= 0)
        {
            a = new BigInteger(n.bitLength(), r).add(two);
        }

        if (! isSpsp(n, a))
        {
            return false;
        }

        k -= 1;
    }

    return true;
}

詳細については、素数によるプログラミングのエッセイを参照してください。

于 2013-01-25T23:47:09.963 に答える