我正在尝试在Ruby 2.1中实现this "find the nth prime number" algorithm。这个天真的素数算法为什么会失败？

我已经标记了'算法'，因为我认为这个问题是语言不可知的，而且即使你不熟悉，所写的Ruby代码也足够简单。我使用了描述性变量名称来帮助它。

遍历整个数字系统，忽略甚至大于号码2（2，3，5，7，...）
对于每个整数，p，检查如果p是素数：
1. 迭代对于已发现的素数小于p的平方根
2. 对于这个集合中的每个素数f，检查它是否是p的因子： i。如果f除p，那么p是非素数。从2继续下一页。
3. 如果找不到任何因素，p就是素数。继续3.
如果p不是我们找到的第n个素数，请将其添加到素数列表中。从2继续下一页。
否则，p是我们找到的第n个素数，我们应该返回它。

听起来很简单。所以我写我的方法（函数）：

def nth_prime(n) 
     primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

     primes[-1].upto(Float::INFINITY) do |p| 
      return primes[n-1] if primes.length >= n-1 
      possible_prime = true 
      primes_to_check = primes.select{|x|x<=Math.sqrt(p)} 
      primes_to_check.each do |f| 
       if f%p==0 
        possible_prime = false 
        break 
       end 
      end 
      primes << p if possible_prime 
     end 
    end

意图是说nth_prime(10)并得到第10个素数。

解释我的逻辑：

我开始已知质数列表，因为算法要求。我列出前十名。

然后我遍历整个数字系统。 (primes[-1]+2).upto(Float::Infinity) do |p|将提供从最后一个已知素数加上两个数字（因为+1将导致偶数并且均匀超过2不能为素数），以无限于p的缩进块。我没有跳过偶数和有

我做的第一件事就是返回ñ个质数，如果已知素数的名单已经至少ň元素长。这对于已知的值是有效的 - 如果你问5号，你将得到11。

然后我将一个标志possible_prime设置为true。这表明没有任何证据证明它是而不是。我要做一些测试，如果它没有改变为false，那么p被证明是质数，并被附加到已知质数阵列。最终该阵列将长达n并返回第n个值。

我创建了一个数组，primes_to_check，包含所有已知的素数< = p的平方根。每个人依次被测试为f。

若f可以清晰地划分p，我知道，p是不是素数，所以我改变标志false，并且break，这给我们带来了素数对循环校验和回到upto-无限循环。在该循环中只剩下一条语句，即如果该标志为真，则追加到已知素数数组中的语句，这不是我们重新启动具有下一个数字的循环。

如果没有f S能干净利落地划分p那么p必须是素的，这意味着它生存的素数 - 校验循环使用仍设置为true的结束标志，并达到最终的“追加p到已知素数的声明。

最终这将使primes数组足够长以回答“什么是第n个素数？”这个问题。

问题

问计于10日黄金确实让我29，上次主我预先提供的。但要求11获得nil，或没有价值。我已经完成了上百次代码，无法想象没有返回值的情况。

我做错了什么？

来源

2015-04-04 GreenTriangle

return primes[n-1] if primes.length >= n-1

对于primes到具有索引n-1的元素，它的长度必须至少n。

if f%p==0

这检查一个已知的素数是否可以被候选人整除，而不是候选人是否可以被已知的素数整除。

primes[-1].upto(Float::INFINITY) do |p|

这开始在列表（29）中已经存在的主要循环。 29被正确地认定为素数，所以它又被添加到列表中。你需要在29之后开始循环。

来源

2015-04-04 07:33:05 user2357112

嗯。良好的发现，我想我正在考虑零索引或那里的东西。但将它改为'n'而不是'n-1'会引入一个新的错误：第11个素数返回第10个，并且每个附加数字只返回下一个整数，而不是下一个素数。 – GreenTriangle 2015-04-04 08:14:16

@GreenTriangle：发现更多的错误。如果还有更多，请在再次询问之前尝试自己找到它们。 – user2357112 2015-04-04 08:25:07

Algorithm for testing prime no.s: 
1)Input num 
2)counter= n-1 
3)repeat 
4)remainder = num%counter 
5)if rem=0 then 
6)broadcast not a prime.no and stop 
7)change counter by -1 
8)until counter = 1 
9)say its a prime and stop

来源

2016-10-05 20:29:00

这个回答怎么样？我做了什么错了？'？这是否找到第n个素数？就像从2开始并且向上一样有效吗？ – greybeard 2016-10-05 21:25:34

是的，当你输入一个数字时，它会告诉你它是否是素数。 – 2016-10-06 14:59:42

第n个素数是别的：如果你输入5，你不应该回答真（或假），2,3,5,7或9，而是'11'，因为它是第五个质数。（无论如何，GreenTriangle的问题仍然是“我做错了什么？”） – greybeard 2016-10-06 16:19:01

这个天真的素数算法为什么会失败？

问题

回答

相关问题