我最近参加了我学校的一个小型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抱歉,如果我的代码格式错误,这是我第一次在这里发帖.此外,输出必须在每一行之后有一个'#'表示循环之后的行是什么感谢您提供的任何帮助!