ruby - 如何找到给定输入值以下的所有素数？

问题描述

我的任务是在 Ruby 中查找所有素数（不使用素数方法）

下面是我的逻辑、问题、代码和输出。

我的逻辑：

所有素数只有 2 个不同的除数。因此，如果我们计算一个数字的除数并且它大于 2，那么它不是素数（除了 1，我还没有处理）

因此我制作了一个数组，用 1 到 10 的所有数字填充它（我稍后会做 1000），并删除所有有超过 2 个除数的数字

问题：

下面的代码似乎没有检查 5,7 或 9。

我的代码（红宝石）

#Create an array that will be your list of prime numbers
primes = [] 
 
#create variables
x = 1
counter = 0
y=1  
 
#fill array with numbers (I'm using 10 rather than 1000 for now)
for x in 1..10 # 1..10 is inclusive in ruby
primes.push(x)  #put x into primes array
end
 
primes.each do |prime_number|  for y in 1..10 do #for each x and each y, do the following
      puts "#{prime_number} , #{y}" #puts is print with a new line
      if prime_number % y == 0   #check if element in array divided by numbers 1-10 is mod 0
        counter +=1   #is so increase counter by 1
        if counter > 2
          primes.delete(prime_number)
          counter = 0   #if counter get's above 2 then number cannot be prime. hence remove it from array
        end
      end
    end
end
 
puts primes  #print out primes to check result
sum_of_primes = primes.inject(:+)  #sum of all primes
puts sum_of_primes #print answer

这是输出：

1 , 1
1 , 2
1 , 3
1 , 4
1 , 5
1 , 6
1 , 7
1 , 8
1 , 9
1 , 10
2 , 1
2 , 2
2 , 3
2 , 4
2 , 5
2 , 6
2 , 7
2 , 8
2 , 9
2 , 10
4 , 1
4 , 2
4 , 3
4 , 4
4 , 5
4 , 6
4 , 7
4 , 8
4 , 9
4 , 10
6 , 1
6 , 2
6 , 3
6 , 4
6 , 5
6 , 6
6 , 7
6 , 8
6 , 9
6 , 10
8 , 1
8 , 2
8 , 3
8 , 4
8 , 5
8 , 6
8 , 7
8 , 8
8 , 9
8 , 10
10 , 1
10 , 2
10 , 3
10 , 4
10 , 5
10 , 6
10 , 7
10 , 8
10 , 9
10 , 10
[1, 3, 5, 7, 9]
25

标签： rubyloopscounterprimes

解决方案

TL;博士

您可以重构迭代器以避免显式循环和计数器。即使您仍在迭代，利用核心方法也可以更快、更容易地进行调试。

为了完整起见，我还提供了一个使用标准库中 Ruby 的Prime模块的示例。这可能是最正确的解决方案，但使用模块是一种在很大程度上完全回避迭代问题的解决方案，至少从实用的角度来看是这样。

简化使用迭代器

如果您的问题是关于功课的，那么我的回答可能无法帮助您学习老师希望您从课程中学到的任何东西。其他答案可能会解释为什么您当前的代码无法按预期工作；相反，我将专注于利用更多 Ruby 核心功能的替代方法。

这是找到给定最大值之前的所有正素数的一种方法：

# Use a Range object to check each Integer between 2 and
# (int - 1) to see if there's a remainder. If not, the value
# of i is added to the anonymous array returned by #map. The
# int is prime if there are no elements in the array.
def prime? int 
  (2...int).none? { |i| int.modulo(i).zero? }
end

# Iterate from 2 to the maximum value, using #select to
# return the subset of values passed to the block where the
# return value of #prime? is truthy.
#
# NB: 1 isn't prime, which is why we start from 2. Reference:
# <https://en.wikipedia.org/wiki/Prime_number#Primality_of_one>
def find_primes max_value
  2.upto(max_value).select { |i| prime? i }
end

find_primes 10
#=> [2, 3, 5, 7]

当然还有其他方法可以做到这一点，但是利用像Array#none这样的内置迭代器？和Array#select同时避免计数器对我来说似乎是一个净赢。你的旅费可能会改变。

使用标准库

作为进一步的简化，您可以简单地使用 Ruby 标准库中的Prime模块。例如，Prime#each返回一个可枚举的Prime::EratosthenesGenerator。然后，您可以调用Enumerable#to_a将结果转换为数组。例如：

require 'prime'

def primes max_value
  Prime.each(max_value).to_a
end

primes 10
#=> [2, 3, 5, 7]