检查int是否更有效率

Question

我最近参加了我学校的一个小型java编程比赛.我的伙伴,我刚刚完成了我们的第一个纯面向对象的类和大多数的问题是我们的联赛,所以我们看中了这一个(和我有点意译):"给定的输入整数n返回下一个int值是素数,例如,如果n = 18,你的程序应该打印31"因为31和13都是素数.然后,您的.class文件将包含一个测试用例,其中包含1-2,000,000,000个传递给它的所有可能数字,并且必须在10秒内返回正确答案才能被视为有效.

我们找到了一个解决方案,但是如果测试用例较大,则需要10秒以上的时间.我相当肯定有一种方法可以将n,... 2,000,000,000的循环范围向下移动,因为当n是一个较小的数字时,需要循环的可能性很小,但是无论哪种方式我们在一个数字时打破了循环在这两种情况下都是素数.起初我们从2开始循环,...无论它有多大,我都记得关于只循环到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抱歉,如果我的代码格式错误,这是我第一次在这里发帖.此外,输出必须在每一行之后有一个'#'表示循环之后的行是什么感谢您提供的任何帮助!

Answer 1

首先,你应该使用像Eratosthenes筛子这样的东西预先计算所有素数高达2,000,000,000 .您可以在位数组中存储每个数字是否为素数.

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

如果由于需要为每个测试用例运行程序的新实例而无法执行此操作,请使用像Miller-Rabin这样的快速素性测试算法.

Answer 2

你的主要检查是非常低效的.实际上,您无需重新检查已检查数字的倍数.因此,当您检查%2时,您无需检查%4.

要确定数字是否为素数,您只需尝试将其除以所有已知质数,直到达到要检查的数字的平方根.这样做可以大大减少分割数量:如果你的应用程序有2 ... ~44721的素数列表(例如计算为准备步骤),你可以很快检查所有数字,直到2000000000.

此外,您应该确保首先检查两个排列中较小的一个(例如,在样本中首先检查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在源中,结果立即显示出来.

Answer 3

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

Answer 4

看起来你要增加 1，但你应该增加 2。除了 2 以外，没有偶数是素数。