55

我试图找到检查给定数字是否为素数的最快方法(在Java中)。以下是我想出的几种素性测试方法。有没有比第二种实现(isPrime2)更好的方法?

public class Prime {
    public static boolean isPrime1(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static boolean isPrime2(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

public class PrimeTest {
    public PrimeTest() {
    }
 
    @Test
    public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
 
        Prime prime = new Prime();
        TreeMap<Long, String> methodMap = new TreeMap<Long, String>();
 
        for (Method method : Prime.class.getDeclaredMethods()) {
 
            long startTime = System.currentTimeMillis();
 
            int primeCount = 0;
            for (int i = 0; i < 1000000; i++) {
                if ((Boolean) method.invoke(prime, i)) {
                    primeCount++;
                }
            }
 
            long endTime = System.currentTimeMillis();
 
            Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
            methodMap.put(endTime - startTime, method.getName());
        }
 
 
        for (Entry<Long, String> entry : methodMap.entrySet()) {
            System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
        }
    }
}
4

15 回答 15

84

这是另一种方式:

boolean isPrime(long n) {
    if(n < 2) return false;
    if(n == 2 || n == 3) return true;
    if(n%2 == 0 || n%3 == 0) return false;
    long sqrtN = (long)Math.sqrt(n)+1;
    for(long i = 6L; i <= sqrtN; i += 6) {
        if(n%(i-1) == 0 || n%(i+1) == 0) return false;
    }
    return true;
}

并且BigInteger's isProbablePrime(...)对所有 32 位有效int

编辑

请注意,isProbablePrime(certainty)这并不总是产生正确的答案。正如@dimo414 在评论中提到的那样,当确定性偏低时,它会产生误报。

不幸的是,我找不到声称isProbablePrime(certainty)对所有 (32-bit) 都有效的来源int(有足够的确定性!)。

所以我做了几个测试。我创建了一个代表所有奇数BitSet的大小,并使用一个素数筛来查找范围内的所有素数。然后我循环测试每个.Integer.MAX_VALUE/21..Integer.MAX_VALUEi=1..Integer.MAX_VALUEnew BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i)

对于确定性 5 和 10,isProbablePrime(...)沿线产生误报。但是isProbablePrime(15),没有测试失败。

这是我的测试台:

import java.math.BigInteger;
import java.util.BitSet;

public class Main {

    static BitSet primes;

    static boolean isPrime(int p) {
        return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
    }

    static void generatePrimesUpTo(int n) {
        primes = new BitSet(n/2);

        for(int i = 0; i < primes.size(); i++) {
            primes.set(i, true);
        }

        primes.set(0, false);
        int stop = (int)Math.sqrt(n) + 1;
        int percentageDone = 0, previousPercentageDone = 0;
        System.out.println("generating primes...");
        long start = System.currentTimeMillis();

        for(int i = 0; i <= stop; i++) {
            previousPercentageDone = percentageDone;
            percentageDone = (int)((i + 1.0) / (stop / 100.0));

            if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                System.out.println(percentageDone + "%");
            }

            if(primes.get(i)) {
                int number = (i * 2) + 1;

                for(int p = number * 2; p < n; p += number) {
                    if(p < 0) break; // overflow
                    if(p%2 == 0) continue;
                    primes.set(p/2, false);
                }
            }
        }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
    }

    private static void test(final int certainty, final int n) {
        int percentageDone = 0, previousPercentageDone = 0;
        long start = System.currentTimeMillis();
        System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
        for(int i = 1; i < n; i++) {
            previousPercentageDone = percentageDone;
            percentageDone = (int)((i + 1.0) / (n / 100.0));
            if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                System.out.println(percentageDone + "%");
            }
            BigInteger bigInt = new BigInteger(String.valueOf(i));
            boolean bigIntSays = bigInt.isProbablePrime(certainty);
            if(isPrime(i) != bigIntSays) {
                System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
                    + bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
                    " a prime");
                return;
            }
        }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
                " minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
    }

    public static void main(String[] args) {
        int certainty = Integer.parseInt(args[0]);
        int n = Integer.MAX_VALUE;
        generatePrimesUpTo(n);
        test(certainty, n);
    }
}

我这样做:

java -Xmx1024m -cp . Main 15

在我的机器上生成素数大约需要 30 秒。iall in的实际测试1..Integer.MAX_VALUE耗时约 2 小时 15 分钟。

于 2010-03-05T10:27:49.647 回答
43

这是最优雅的方式:

public static boolean isPrime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

Java 1.4+。不需要进口。

这么短。如此美丽。

于 2010-12-23T03:42:29.333 回答
12

你迈出了消除所有 2 的倍数的第一步。

然而,你为什么停在那里?您可以消除除 3 之外的所有 3 的倍数,除 5 之外的所有 5 的倍数,等等。

当你按照这个推理得出结论时,你就得到了埃拉托色尼筛

于 2010-03-05T10:19:29.590 回答
12

查看AKS 素性测试(及其各种优化)。它是在多项式时间内运行的确定性素性检验。

图宾根大学(德国)在这里用 Java 实现了该算法

于 2010-03-05T10:24:01.417 回答
5

由于 Jaeschke (1993) 的快速测试是 Miller-Rabin 测试的确定性版本,它没有低于 4,759,123,141 的误报,因此可以应用于 Java int

// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
  int m = 0;
  if ((n&0xffff) == 0) {
    n >>= 16;
    m += 16;
  }
  if ((n&0xff) == 0) {
    n >>= 8;
    m += 8;
  }
  if ((n&0xf) == 0) {
    n >>= 4;
    m += 4;
  }
  if ((n&0x3) == 0) {
    n >>= 2;
    m += 2;
  }
  if (n > 1) {
    m++;
  }
  return m;
}

// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
  BigInteger bigB = BigInteger.valueOf(base);
  BigInteger bigE = BigInteger.valueOf(exponent);
  BigInteger bigM = BigInteger.valueOf(m);
  BigInteger bigR = bigB.modPow(bigE, bigM);
  return bigR.intValue();
}

// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
  int s = val2(n-1);
  int d = modPow(base, n>>s, n);
  if (d == 1) {
    return true;
  }
  for (int i = 1; i < s; i++) {
    if (d+1 == n) {
      return true;
    }
    d = d*d % n;
  }
  return d+1 == n;
}

public static boolean isPrime(int n) {
  if ((n&1) == 0) {
    return n == 2;
  }
  if (n < 9) {
    return n > 1;
  }

  return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}

这不适用于long变量,但不同的测试可以:BPSW 测试没有反例高达 2^64。这基本上包括一个像上面这样的 2-strong probable prime test,然后是一个强 Lucas 测试,它有点复杂但没有根本的不同。

这两项测试都比任何类型的试验部门都要快得多。

于 2017-01-30T22:21:38.120 回答
4

您的算法适用于相当小的数字。对于大数字,应使用高级算法(例如基于椭圆曲线)。另一个想法是使用一些“伪素数”测试。这些将快速测试一个数字是否为素数,但它们不是 100% 准确的。但是,它们可以帮助您比使用算法更快地排除一些数字。

最后,尽管编译器可能会为您优化,但您应该编写:

int max =  (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
于 2010-03-05T10:21:58.240 回答
4

如果您只是想找出一个数字是否是素数,那就足够了,但是如果您想找到从 0 到 na 的所有素数,更好的选择是Eratosthenes 筛

但这将取决于java对数组大小等的限制。

于 2010-03-05T10:23:03.183 回答
4

我认为这种方法是最好的。至少对我来说-

    public static boolean isPrime(int num)
    {
        for (int i = 2; i<= num/i; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }
        return num > 1;
    }
于 2014-11-02T14:09:40.047 回答
4

当然,有数百种素性检验,根据数的大小、特殊形式、因子大小等,都有各种优缺点。

但是,在 java 中,我发现最有用的是:

BigInteger.valueOf(long/int num).isProbablePrime(int certainty);

它已经实现了,而且速度非常快(我发现一个 1000x1000 的矩阵填充了 0-2^64 并且确定性为 15 大约需要 6 秒),并且可能比我们凡人想出的任何东西都得到更好的优化。

它使用了Baillie-PSW primality test的一个版本,它没有已知的反例。(尽管它可能使用稍弱的测试版本,有时可能会出错。也许)

于 2017-03-23T23:46:32.060 回答
3

您所写的是大多数普通程序员所做的,并且在大多数情况下应该足够了。

但是,如果您追求的是“最佳科学算法”,那么在http://en.wikipedia.org/wiki/Prime_number中记录了许多变体(具有不同程度的确定性) 。

例如,如果你有一个 70 位数字,JVM 的物理限制会阻止你的代码运行,在这种情况下你可以使用“Sieves”等。

同样,就像我说的,如果这是一个编程问题或软件中的一般使用问题,你的代码应该是完美的:)

于 2010-03-05T10:20:22.617 回答
3

根据您需要测试的数字的长度,您可以预先计算小值(n < 10^6)的素数列表,如果要求的数字在此范围内,则首先使用该列表。这当然是最快的方法。就像在其他答案中提到的那样,Eratosthenes 的筛子是生成这种预先计算的列表的首选方法。

如果你的数字大于这个,你可以使用拉宾的素数测试。 拉宾素性检验

于 2010-03-05T10:23:11.513 回答
1

算法效率:O( n^(1/2)) 算法

注意:下面的示例代码包含计数变量和对打印函数的调用以打印结果:

import java.util.*;

class Primality{
    private static void printStats(int count, int n, boolean isPrime) {

        System.err.println( "Performed " + count + " checks, determined " + n
        + ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
    }
    /**
    *   Improved O( n^(1/2)) ) Algorithm
    *    Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
    *    The only way to improve on this is to check if n is divisible by 
    *   all KNOWN PRIMES from 2 to sqrt(n).
    *
    *   @param n An integer to be checked for primality.
    *   @return true if n is prime, false if n is not prime.
    **/
    public static boolean primeBest(int n){
        int count = 0;
        // check lower boundaries on primality
        if( n == 2 ){ 
            printStats(++count, n, true);
            return true;
        } // 1 is not prime, even numbers > 2 are not prime
        else if( n == 1 || (n & 1) == 0){
            printStats(++count, n, false);
            return false;
        }

        double sqrtN = Math.sqrt(n);
        // Check for primality using odd numbers from 3 to sqrt(n)
        for(int i = 3; i <= sqrtN; i += 2){
            count++;
            // n is not prime if it is evenly divisible by some 'i' in this range
            if( n % i == 0 ){ 
                printStats(++count, n, false);
                return false;
            }
        }
        // n is prime
        printStats(++count, n, true);
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            int n = scan.nextInt();
            primeBest(n);
            System.out.println();
        }
        scan.close();
    }
}

当输入质数 2147483647 时,它会产生以下输出:

执行了 23170 次检查,确定 2147483647 是 PRIME。

于 2017-01-30T16:15:21.757 回答
0

一般来说,所有大于某个原始整数的素数都具有where和are integersC的形式Ck+i,表示与互质的数i < CikiC

这是一个示例C=30,它应该比 Bart Kiers 回答的更快C=6,您可以通过计算来改进它C=210

boolean isPrime(long n) {
    if(n < 2){
        return false;
    }
    if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19 || n == 23 || n == 29){
        return true;
    }
    
    long sqrtN = (long) Math.sqrt(n) + 1;
    int[] mods = {1, 7, 11, 13, 17, 19, 23, 29};
    for (long i = 30L; i <= sqrtN; i += 30) {
        for (int mod : mods) {
            if(n % (i + mod) == 0){
                return false;
            }
        }
    }
    return true;
}
于 2020-08-07T17:25:58.540 回答
0

首先,素数从 2 开始。2 和 3 是素数。素数不能被 2 或 3 整除。其余素数的形式为 6k-1 和 6k+1。请注意,您应该检查直到 SQRT(input) 的数字。这种方法非常有效。我希望它有所帮助。

public class Prime {

    public static void main(String[] args) {
        System.out.format("%d is prime: %s.\n", 199, isPrime(199)); // Prime
        System.out.format("%d is prime: %s.\n", 198, isPrime(198)); // Not prime
        System.out.format("%d is prime: %s.\n", 104729, isPrime(104729)); // Prime
        System.out.format("%d is prime: %s.\n", 104727, isPrime(982443529)); // Prime
    }

    /**
     * Tells if a number is prime or not.
     *
     * @param input the input
     * @return If the input is prime or not
     */
    private boolean isPrime(long input) {
    if (input <= 1) return false; // Primes start from 2
    if (input <= 3) return true; // 2 and 3 are primes
    if (input % 2 == 0 || input % 3 == 0) return false; // Not prime if dividable by 2 or 3
    // The rest of the primes are in the shape of 6k-1 and 6k+1
    for (long i = 5; i <= Math.sqrt(input); i += 6) if (input % i == 0 || input % (i + 2) == 0) return false;
    return true;
    }

}
于 2020-04-21T17:24:23.500 回答
0

在 Intel Atom @ 1.60GHz、2GB RAM、32 位操作系统中测试

测试结果:
Long.MAX_VALUE=9223372036854775807以下的最大素数是9223372036854775783
经过的时间是171499毫秒或2分51秒

public class PrimalityTest
{
    public static void main(String[] args)
    {
        long current_local_time = System.currentTimeMillis();
        long long_number = 9223372036854775783L;
        long long_a;
        long long_b;
        if (long_number < 2)
        {
            System.out.println(long_number + " is not a prime number");
        }
        else if (long_number < 4)
        {
            System.out.println(long_number + " is a prime number");
        }
        else if (long_number % 2 == 0)
        {
            System.out.println(long_number + " is not a prime number and is divisible by 2");
        }
        else
        {
            long_a = (long) (Math.ceil(Math.sqrt(long_number)));
            terminate_loop:
            {
                for (long_b = 3; long_b <= long_a; long_b += 2)
                {
                    if (long_number % long_b == 0)
                    {
                        System.out.println(long_number + " is not a prime number and is divisible by " + long_b);
                        break terminate_loop;
                    }
                }
                System.out.println(long_number + " is a prime number");
            }
        }
        System.out.println("elapsed time: " + (System.currentTimeMillis() - current_local_time) + " millisecond/s");
    }
}
于 2018-09-27T02:47:47.120 回答