java 更有效地检查 int 是否为素数

Checking if an int is prime more efficiently

提问by SipSop

I recently was part of a small java programming competition at my school. My partner and I have just finished our first pure oop class and most of the questions were out of our league so we settled on this one (and I am paraphrasing somewhat): "given an input integer n return the next int that is prime and its reverse is also prime for example if n = 18 your program should print 31" because 31 and 13 are both prime. Your .class file would then have a test case of all the possible numbers from 1-2,000,000,000 passed to it and it had to return the correct answer within 10 seconds to be considered valid.

我最近参加了我学校的一个小型 Java 编程比赛。我和我的搭档刚刚完成了我们的第一个纯 oop 课程，大部分问题都超出了我们的范围，所以我们解决了这个问题（我稍微解释了一下）：“给定一个输入整数 n 返回下一个整数，它是质数，并且它的反面也是素数，例如如果 n = 18 你的程序应该打印 31" 因为 31 和 13 都是素数。然后，您的 .class 文件会将 1-2,000,000,000 中所有可能数字的测试用例传递给它，并且它必须在 10 秒内返回正确答案才能被视为有效。

We found a solution but with larger test cases it would take longer than 10 seconds. I am fairly certain there is a way to move the range of looping from n,..2,000,000,000 down as the likely hood of needing to loop that far when n is a low number is small, but either way we broke the loop when a number is prime under both conditions is found. At first we were looping from 2,..n no matter how large it was then i remembered the rule about only looping to the square root of n. Any suggestions on how to make my program more efficient? I have had no classes dealing with complexity analysis of algorithms. Here is our attempt.

我们找到了一个解决方案，但对于更大的测试用例，它会花费超过 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;
  }
}

ps sorry if i did the formatting for code wrong this is my first time posting here. Also the output had to have a '#' after each line thats what the line after the loop is about Thanks for any help you guys offer!!!

ps 抱歉，如果我的代码格式错误，这是我第一次在这里发帖。此外，输出必须在每行之后有一个“#”，这就是循环之后的行的含义 感谢你们提供的任何帮助！！！

回答by David

First you should precompute all prime numbers up to 2,000,000,000 using something like the Sieve of Eratosthenes. You can store whether each number is prime in a bit array.

首先，您应该使用诸如埃拉托色尼筛之类的东西预先计算最多 2,000,000,000 的所有素数。您可以将每个数字是否为素数存储在位数组中。

This is pretty fast, and then checking each individual number for primality is a simple lookup.

这非常快，然后检查每个单独的数字的素数是一个简单的查找。

If you can't do this because you need to run a new instance of your program for each test case, use a fast primality testing algorithm like Miller-Rabin.

如果您因为需要为每个测试用例运行一个新的程序实例而无法执行此操作，请使用快速素性测试算法，例如Miller-Rabin。

回答by Lucero

Your prime check is very inefficient. In fact, you don't need to re-check multiples of already checked numbers. So when you check for %2, you don't need to check for %4.

你的主要检查是非常低效的。事实上，您不需要重新检查已经检查过的数字的倍数。因此，当您检查 %2 时，您不需要检查 %4。

To find out whether a number is a prime, you only have to try to divide it by all known primes until you reach the square root of the number to be checked. Doing this reduces the number of divisions vastly: if your app has a list of the primes from 2..~44721 (for instance computed as preparation step), you can check all numbers until 2000000000 pretty quickly.

要确定一个数是否是素数，您只需尝试将其除以所有已知素数，直到达到要检查的数的平方根。这样做可以大大减少除法的数量：如果您的应用程序有一个 2..~44721 的素数列表（例如作为准备步骤计算），您可以很快检查到 2000000000 之前的所有数字。

Also, you should make sure to check the smaller of the two permutations first (e.g. in your sample first check 13, then 31).

此外，您应该确保首先检查两个排列中较小的一个（例如，在您的样本中首先检查 13，然后是 31）。

Edit:

编辑：

Here's a sample I quickly put together in C# (you'll need to do some minor syntactic changes to have it run on Java, but I just had a C# compiler at hand):

这是我在 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);
}

On my computer and with the given loopand nin the source the result shows up instantaneous.

在我的计算机上，使用给定的loop和n源中的结果立即显示。

回答by Stephen Denne

Using BigInteger.isProbablePrime(certainty)and BigInteger.nextProbablePrime()can significantly cut down the number of cases you need to check quite efficiently

使用BigInteger.isProbablePrime(certainty)和BigInteger.nextProbablePrime()可以显着减少您需要非常有效地检查的案例数量

回答by Mantas Vidutis

It seems like you are incrementing by 1, but you should be incrementing by 2. No even number is prime but 2.

看起来你增加了 1，但你应该增加 2。没有偶数是质数，只有 2。

回答by spender

The big inefficiency here is your prime testing method prime. Take a think about the number of times it will have to test the very same numbers, and concentrate on how one might take advantage of memory structures in order to avoid some of the repeated calculations.

这里最大的低效率是您的主要测试方法prime。考虑一下必须测试相同数字的次数，并专注于如何利用内存结构来避免一些重复计算。

回答by HansDampf

I havent done this before, but here are some things that come to my mind.

我以前没有这样做过，但这里有一些事情浮现在我的脑海中。

if your squareroot is a integer it the number is not prime

如果您的平方根是整数，则该数字不是素数

if the number ends in a 0,2,4,5,6, or 8 it is not prime /except 2 itself

如果数字以 0、2、4、5、6 或 8 结尾，则它不是质数/除了 2 本身

Number can be divided by 3 if the sum ofdigits is divisible by 3 and by 9 if sum is 9.

如果数字之和能被 3 整除，则数字可以被 3 整除；如果数字之和是 9，则可以被 9 整除。

I dont know wether testing for this things help you, at least the test of the squareRoot should help because you have to compute it anyway and you can be done already.

我不知道测试这些东西是否对你有帮助，至少 squareRoot 的测试应该有帮助，因为无论如何你必须计算它并且你已经可以完成了。

Oh and ofcourse your efficence will increase a lot if you do something like Miller–Rabin primality test http://en.wikipedia.org/wiki/Miller-Rabin_primality_test. Your actual test only needs to be done in the cases that arent certain.

哦，当然，如果你做类似 Miller-Rabin 素数测试http://en.wikipedia.org/wiki/Miller-Rabin_primality_test这样的事情，你的效率会提高很多。您的实际测试只需要在不确定的情况下进行。

回答by outis

Another speed improvement you can make in mainis to change your loop to pre-filter some composite numbers, unrolling some iterations into a sequence of tests. The simplest is to test 2 outside the loop, then test odd numbers (2*i+1). Slightly more complex is to test 2, 3, then 6*i ± 1. You can keep extending this approach, testing the first n primes, then looping oven pn# * i+j, where p_n#is the prime primordial(the product of the first n primes) and j is a positive integer less than and coprime to p_n#.

您可以进行的另一个速度改进main是更改循环以预过滤一些合数，将一些迭代展开为一系列测试。最简单的是在循环外测试 2，然后测试奇数 ( 2*i+1)。稍微复杂一点的是测试 2, 3, then 6*i ± 1。您可以继续扩展这种方法，测试前 n 个素数，然后循环烤箱，其中p _n#是素数原初（前 n 个素数的乘积），j 是小于 p _n#且互质的正整数。pn# * i+j

To speed up the primemethod, you could start with a fast probabilistic prime testand test using a slower deterministic test only for those cases the probabilistic test can't determine.

为了加速该prime方法，您可以从快速概率素数测试开始，然后仅针对概率测试无法确定的情况使用较慢的确定性测试进行测试。

回答by Graham

Even faster than all of that is using the Miller-Rabintest. It's a probabilistic test, and therefore has a certain level of error; however, the test runs multiple times which shrinks that error as small as needed (50 often suffices for commercial applications).

甚至比使用Miller-Rabin测试更快。这是一个概率测试，因此有一定程度的误差；但是，该测试运行多次，从而根据需要将错误缩小到最小（对于商业应用程序通常 50 次就足够了）。

Not in Java, but here'sa quick implementation in Python I cooked up.

不是在 Java 中，但这是我在 Python 中编写的快速实现。

回答by SipSop

@outis...i see what you are saying thats a neat little trick i must say. thank you for that.

@outis...我明白你在说什么，这是我必须说的一个巧妙的小技巧。谢谢你。

@Graham...also cool i read an article on the test you mentioned because although I think i understood the gist of it from the comments you made Python always looks like greek to me. I know everyone says its one of the simpler languages to pick up but for whatever reason java and c++ always look more readable to me. Anyway, yea that wouldve been a much better way to do it. Thanks again to all of you who gave me tips I learned alot from this board. Can't for my data structures and algorithms class in the fall!!!

@Graham ...也很酷，我读了一篇关于你提到的测试的文章，因为虽然我认为我从你所做的评论中理解了它的要点，但 Python 对我来说总是看起来像希腊语。我知道每个人都说它是一种更简单的语言，但无论出于何种原因，java 和 c++ 对我来说总是更具可读性。无论如何，是的，这是一个更好的方法。再次感谢所有给我提示的人，我从这个板上学到了很多东西。不能参加我秋季的数据结构和算法课！！！

回答by ioquatix

The easiest option would be use use an existing big integer library. It won't have bugs, and it will provide all the supporting functions.

最简单的选择是使用现有的大整数库。它不会有错误，并且会提供所有的支持功能。

If you are writing your own implementation (i.e. for an assignment), I'd recommend working from a pseudo code algorithm in a book so that you understand what you are doing.

如果您正在编写自己的实现（即用于作业），我建议您使用书中的伪代码算法进行工作，以便您了解自己在做什么。

That being said, one of the simplest methods is to use Jacobi and Legendre, and compare for equality. I just submitted an assignment for RSA encryption. Here is what I did for single precision, however the algorithms are general and work for multiple precision integers too.

话虽如此，最简单的方法之一是使用 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;
}

Performance is very good even with large numbers.

即使数量很大，性能也非常好。