检查int是否更有效率
我最近参加了我学校的一个小型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=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抱歉，如果我的代码格式错误，这是我第一次在这里发帖。 此外，输出必须在每一行之后有一个’＃’表示循环之后的行是什么感谢您提供的任何帮助！
首先，你应该使用像Eratosthenes筛子这样的东西预先计算所有素数高达2,000,000,000。 您可以在位数组中存储每个数字是否为素数。
这非常快，然后检查每个单独的数字的素数是一个简单的查找。
如果由于需要为每个测试用例运行程序的新实例而无法执行此操作，请使用像Miller-Rabin这样的快速素性测试算法。
你的主要检查是非常低效的。 实际上，您无需重新检查已检查数字的倍数。 因此，当您检查％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 ，结果立即显示出来。
使用BigInteger.isProbablePrime(certainty)和BigInteger.nextProbablePrime()可以显着减少需要非常有效地检查的案例数量
看起来你增加1，但你应该增加2.没有偶数是素数而是2。
这里的低效率是你的主要测试方法。 考虑一下测试相同数字所需的次数，并集中精力研究如何利用内存结构来避免一些重复计算。
我之前没有这样做，但这里有一些我想到的事情。
如果你的squareroot是一个整数，那么这个数字不是素数
如果数字以0,2,4,5,6或8结尾，那么它本身不是素数/ 2
如果数字的总和可以被3整除，则数字可以除以3，如果和为9则数字可以除以9。
我不知道这些东西的测试对你有帮助，至少squareRoot的测试应该有所帮助，因为无论如何你必须计算它并且你已经可以完成了。
哦，当然，如果你做像Miller-Rabin素性测试http://en.wikipedia.org/wiki/Miller-Rabin_primality_test这样的事情，你的效率会增加很多。 您的实际测试只需要在不确定的情况下完成。
您可以在main中进行的另一个速度改进是更改循环以预过滤某些复合数字，将一些迭代展开到一系列测试中。 最简单的是在循环外测试2，然后测试奇数（ 2*i+1 ）。 稍微复杂的是测试2,3，然后6*i ± 1 。 您可以继续扩展这种方法，测试前n个素数，然后循环烤箱p n # * i+j ，其中p n ＃是素数原始 （前n个素数的乘积），j是小于和的正整数互质互惠。
为了加速prime方法，您可以从快速概率素数测试开始，并使用较慢的确定性测试仅针对概率测试无法确定的情况进行测试。
@outis …我明白你说的是我必须说的一个巧妙的小技巧。 谢谢你。
@Graham …也很酷我读了一篇关于你提到的测试的文章，因为虽然我认为我从你的评论中理解了它的主旨，Python对我来说总是看起来像希腊语。 我知道每个人都说它是一种比较简单的语言，但无论出于何种原因，java和c ++总是让我看起来更具可读性。 无论如何，是的，这将是一个更好的方式来做到这一点。 再次感谢所有给我提示的人，我从这个板上学到了很多东西。 秋天不能为我的数据结构和算法类！
最简单的选择是使用现有的大整数库。 它不会有错误，它将提供所有支持function。
如果您正在编写自己的实现（即作业），我建议您使用书中的伪代码算法，以便了解自己在做什么。
话虽这么说，最简单的方法之一是使用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; }
即使数量很大，性能也非常好。
@David获取数字的平方根，然后循环直到平方根消除偶数并查看它是否不可分割
甚至比使用Miller-Rabin测试更快。 这是一个概率测试，因此具有一定的误差水平; 然而，测试运行多次，这使得该误差缩小到所需的小（50通常足以满足商业应用）。
不是Java，但这是我在Python中快速实现的。