草庐IT

关于素数：代码不会停止运行，在 Java 中

codeneng 2023-03-28 原文

the code doesn't stop running, in Java

我正在用 Java 解决项目 Euler 中的问题 10，即

"The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million."

我的代码是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package projecteuler_1;

import java.math.BigInteger;
import java.util.Scanner;

public class ProjectEuler_1 {

 public static void main(String[] args) {
    int sum = 0, i = 2;
    while (i <= 2000000) {
        if (isPrime(i)) {
            sum += i;
        }
        i++;
    }
    System.out.println(sum);
 }

 public static boolean isPrime(int n) {
    int i, res;
    boolean flag = true;
    for (i = 2; i <= n / 2; i++) {
        res = n % i;
        if (res == 0) {
            flag = false;
            break;
        }
    }
    return flag;
 }
}

但是代码没有给我任何结果，它没有停止运行。为什么？

  • 代码在 O(n^2) 中，可能需要很长时间。确定完成了吗？
  • 它打印什么？或者你是说它根本不打印任何东西？首先尝试使用更小的数字 - 正如@Absurd-Mind 所说，这可能需要很长时间。
  • 一定需要时间。
  • 它没有给你任何结果的原因是它的优化非常糟糕。 Project Euler 旨在针对需要它的问题优化您的算法，因此您的代码是解决方案过于简单而无法提供解决方案的主要示例。您需要制定另一种方法，但将其作为答案会破坏挑战。
  • 它会完成，但需要很长时间。您应该考虑一些加快代码速度的捷径。例如： isPrime() 是否必须检查 n 下的所有数字，还是一个子集就足够了？也许你可以早点离开这个功能？等等 ...
  • @Absurd-Mind 不，虽然代码是正确的，但它没有完成，你怎么知道它在 O(n^2) 中？ :)
  • 您是否尝试调试它？我和@Absurd-Mind 在一起，我相信它正在运行，但速度很慢。 2,000,000^2 = 4,000,000,000,000，这是很多
  • @user3605253 尝试一个较小的数字，看看它是否真的运行正确。
  • @user3605253 通过查看它。两个 while/for 循环表明它将是 n^2。尝试较小的数字或在 if (isPrime(n)) { print... 内添加打印
  • 你知道 BigInteger 有自己的检查素数的方法吗？查看 BigInteger::isProbablePrime。
  • 感谢@WillNess ....！
  • @?·?§ù??± 不需要，真的。但不客气。 -- 为什么要删除你的答案？我希望您已经进行了最后一次更正，因此这里至少有一个正确的代码，我可以对其进行投票。如果你这样做，请联系我。
  • 在此搜索之前，此搜索提供了 15 个关于 SO 上有关此问题的问题。
  • 我试图在 Java 中找到低于 200 万的素数之和的可能重复项
  • @user3605253 遇到明显的非终止问题时，应用增长分析的经验顺序。为一些较小的 n 运行您的程序，您将在 1..10..100 秒范围内获得运行时间，然后为您的 n 进行投影。 -- 至于你的代码，将你的 sum 设为 long 变量，而不是 int，然后在 isPrime() 函数中将 for (i = 2; i <= n / 2; i++) { 更改为 for (i = 2; i <= n / i; i++) {，它会为你工作。

通过一个小小的改变，你可以极大地提高性能：

变化：

1
for (int i = 2; i < n; i++) {

收件人：

1
2
int max = Math.sqrt(n);
for (int i = 2; i <= max; i++) {

你只需要检查到数字的平方根，因为在上升的过程中已经发现了更大的因素。

进行此更改会将您的算法从 O(n2) 更改为 O(n log(n))(我认为)。您的代码没有输出任何内容，因为运行时间太长 - 更改应该有望在合理的时间内为您提供答案。

  • 我很想问为什么 OP 要检查偶数。如果它不除以 2，为什么它会除以 4？解决方案中还有其他问题，但我想我会把它留给 OP 去发现。
  • @eis 您还可以进行其他优化，但即使您建议的优化也不会改变大 O 数。
  • 是的，它没有。但是我认为我们不应该为他解决问题，因为 Project Euler 是关于个人学习的，真的。我认为他的算法次优的暗示应该足够了。
  • 它将是 O(nsqrt(n))，而不是 O(nlogn)。为了推理，我在这个线程中给出了详细的答案。
  • 仅供参考，所述问题是它"不会停止运行"，而不是"给出错误的结果"。我相信我已经回答了上述问题并提供了解决方案。
  • (这并不能修复产生不正确结果的 OP 代码......只是提到它，因为这是一个公认的答案)。

您的代码运行时间是 O(n^2)。对 isPrime() 的每次调用平均为 O(n)。

解释：

1/2 可以被 2 整除，1/3 可以被 3 整除，... 1/n 可以被 n 整除。该方法的预期运行次数将是 (1-1/2) + (1-1/3) +...+(1-1/n) = (1+1+..+1)-(1/2+1/3+..+1/n) = n - (1/2+1/3+...+1/n) 第二个和是谐波数，它的和在 O(logn) 中，所以这给了你 O(n-logn)=O(n) 运行时间。

由于这是针对每个数字完成的，因此总共会给出 O(n^2).

@Bohemian 更改为 int max = Math.sqrt(n); 的方法将产生 O(nsqrt(n)) 性能，如该线程中所述。

就时间复杂度而言，最好的方法是使用像 Sieve of Eratosthenes 之类的东西，它会产生 O(nlogn) 时间性能，这在渐近上优于您的算法和优化的算法，因此对于大型算法运行速度会明显更快数字。

Java关于spanclassnbspjavaprimes

有关关于素数：代码不会停止运行，在 Java 中的更多相关文章

  1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  2. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  3. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  4. ruby - 如何每月在 Heroku 运行一次 Scheduler 插件？ - 2

    在选择我想要运行操作的频率时，唯一的选项是“每天”、“每小时”和“每10分钟”。谢谢!我想为我的Rails3.1应用程序运行调度程序。 最佳答案 这不是一个优雅的解决方案，但您可以安排它每天运行，并在实际开始工作之前检查日期是否为当月的第一天。 关于ruby-如何每月在Heroku运行一次Scheduler插件？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/8692687/

  5. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  6. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

  7. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  8. ruby-on-rails - 项目升级后 Pow 不会更改 ruby​​ 版本 - 2

    我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby​​版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby​​版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘

  9. ruby - Sinatra:运行 rspec 测试时记录噪音 - 2

    Sinatra新手；我正在运行一些rspec测试，但在日志中收到了一堆不需要的噪音。如何消除日志中过多的噪音？我仔细检查了环境是否设置为:test，这意味着记录器级别应设置为WARN而不是DEBUG。spec_helper:require"./app"require"sinatra"require"rspec"require"rack/test"require"database_cleaner"require"factory_girl"set:environment,:testFactoryGirl.definition_file_paths=%w{./factories./test/

  10. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

随机推荐