草庐IT

java - 解释Euler's Totient Implementation的实现

coder 2024-03-19 原文

我在一个编码平台上看到这段代码可以有效地计算不同值的欧拉 totient。 我无法理解这个实现。我真的很想学这个。谁能帮我解释一下？

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

最佳答案

首先，让我们注意对于质数 p，phi(p) = p - 1。这应该是相当直观的，因为所有小于质数的数字都必须与所述质数互质。那么我们开始进入我们的外部 for 循环:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;

这里我们将i的值添加到phi(i)。对于主要情况，这意味着我们需要预先使 phi(i) 等于 -1，并且必须调整所有其他 phi(i)进一步考虑互质整数的数量。关注主要情况，让我们说服自己这些确实等于 -1。

如果我们单步执行循环，在 i=1 的情况下，我们最终将遍历内部循环中的所有其他元素，减去 1。 

   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }

要减去任何其他值，j 必须等于素数 p。但这需要 j = 2 * i + i * k 等于 p，对于某些迭代 k。这不可能，因为 2 * i + i * k == i * (2 + k) 暗示 p 可以被 i，它不能(因为它的主要部分)。因此，所有 phi(p) = p - 1。

对于非素数i，我们需要减去互素整数的个数。我们在内部 for 循环中执行此操作。重复使用之前的公式，如果 i 除以 j，我们得到 j/i = (2 + k)。所以每个小于 i 的值都可以乘以 (2 + k) 以小于 j，但有一个公因数 (2 + k) 与 j(因此，不是互质)。

但是，如果我们减去包含 (2 + k) 因子的 (i - 1) 倍数，我们将多次计算相同的因子。相反，我们只计算与 i 互质的那些，或者换句话说 phi(i)。因此，我们剩下 phi(x) = x - phi(factor_a) - phi(factor_b) ... 来解释所有 (2 + k_factor) 倍数小于所述因子的互质数，现在与 x 共享一个因子 (2 + k_factor)。

将其放入代码中可以为我们提供上述内容:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

关于java - 解释Euler's Totient Implementation的实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55170094/

ImplementationTotientcode互质phijavaalgorithmmath

有关java - 解释Euler's Totient Implementation的实现的更多相关文章

  1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  2. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  3. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  4. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  5. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  6. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

    我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

  7. ruby-on-rails - 新 Rails 项目 : 'bundle install' can't install rails in gemfile - 2

    我已经像这样安装了一个新的Rails项目:$railsnewsite它执行并到达:bundleinstall但是当它似乎尝试安装依赖项时我得到了这个错误Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcheckingforlibkern/OSAtomic.h...yescreatingMakefilemake"DESTDIR="cleanmake"DESTDIR="

  8. 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/

  9. ruby-on-rails - rspec should have_select ('cars' , :options => ['volvo' , 'saab' ] 不工作 - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request

  10. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

随机推荐