8

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

我们找到了一个解决方案，但是对于更大的测试用例，它需要超过 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 抱歉，如果我的代码格式错误，这是我第一次在这里发帖。此外，输出必须在每行之后有一个“#”，这就是循环之后的行的含义。感谢你们提供的任何帮助！！！

4

11 回答 11

17

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

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

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

于 2010-05-05T23:51:59.880 回答
7

您的主要检查非常低效。事实上，您不需要重新检查已检查号码的倍数。因此，当您检查 %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源代码，结果会立即显示出来。

于 2010-05-05T23:53:39.223 回答
5

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

于 2010-05-05T23:58:37.320 回答
4

看起来你正在增加 1，但你应该增加 2。没有偶数是素数，而是 2。

于 2010-05-05T23:51:35.433 回答
0

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

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

于 2010-05-06T02:28:56.893 回答
0

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

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

于 2010-05-10T00:27:01.697 回答
0

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

于 2010-05-05T23:53:23.287 回答
0

@David 得到一个数的平方根，然后循环直到平方根消除偶数，看看它是否不可整除

于 2010-09-08T11:14:01.577 回答
0

我以前没有这样做过，但是我想到了一些事情。

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

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

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

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

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

于 2010-05-05T23:59:46.133 回答
0

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

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

于 2010-05-11T04:02:11.900 回答
0

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

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

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

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

于 2010-09-08T10:45:39.737 回答