我最近参加了学校的小型 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/
给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案
我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查
我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/
这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下