我最近参加了学校的小型 Java 编程竞赛。我和我的搭档刚刚完成了我们的第一个纯 oop 类(class)，大部分问题都超出了我们的范围，所以我们选择了这个(我稍微解释了一下):“给定一个输入整数 n 返回下一个素数 int 和它的反面也是质数，例如，如果 n = 18，您的程序应该打印 31"，因为 31 和 13 都是质数。然后，您的 .class 文件将传递一个包含 1-2,000,000,000 之间所有可能数字的测试用例，并且它必须在 10 秒内返回正确答案才能被视为有效。
我们找到了解决方案，但如果测试用例较大，则需要 10 秒以上的时间。我相当确定有一种方法可以将循环范围从 n,..2,000,000,000 向下移动，因为当 n 是一个小数字时需要循环那么远的可能性很小，但是无论哪种方式我们都会在数字时打破循环在两种情况下都是素数。起初我们从 2,..n 开始循环，不管它有多大然后我想起了关于只循环到 n 的平方根的规则。关于如何使我的程序更有效率的任何建议？我没有上过处理算法复杂性分析的类(class)。这是我们的尝试。
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 抱歉，如果我的代码格式有误，这是我第一次在这里发帖。此外，输出必须在每一行之后有一个“#”，这就是循环之后的行的内容感谢你们提供的任何帮助!!!
最佳答案
首先，您应该使用 Sieve of Eratosthenes 之类的方法预先计算不超过 2,000,000,000 的所有质数。 .您可以将每个数字是否为素数存储在一个位数组中。
这非常快，然后检查每个数字的素数是一个简单的查找。
如果因为需要为每个测试用例运行一个新的程序实例而无法执行此操作，请使用像 Miller-Rabin 这样的快速素数测试算法。 .
关于java - 更有效地检查 int 是否为素数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2777509/