ruby - 质数和
问题描述
因此,我在 HackerRank 上完成了其中一项编程挑战,以帮助培养我的技能。(不,这不是面试!我遇到的问题是素数和。(完整描述:https ://www.hackerrank.com/challenges/prime-digit-sums/problem )基本上给定一个值n
,我am 找出所有满足以下三个条件的 n 位数字:
- 每 3 个连续数字总和为一个素数
- 每 4 个连续数字总和为一个素数
- 每 5 个连续数字总和为一个素数
详细分解见链接...
我有一个可以工作的基本功能,问题是当n
它变得足够大时它会中断:
#!/bin/ruby
require 'prime'
def isChloePrime?(num)
num = num.to_s
num.chars.each_cons(5) do |set|
return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
end
num.chars.each_cons(4) do |set|
return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
end
num.chars.each_cons(3) do |set|
return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
end
return true
end
def primeDigitSums(n)
total = 0
(10**(n-1)..(10**n-1)).each do |i|
total += 1 if isChloePrime?(i)
end
return total
end
puts primeDigitSums(6) # prints 95 as expected
puts primeDigitSums(177779) # runtime error
如果有人能指出我正确的方向,那就太棒了。不一定要寻找“这就是答案”。理想情况下会喜欢“尝试使用此功能......”。
这里的更新是第 2 版:
#!/bin/ruby
require 'prime'
@primes = {}
def isChloePrime?(num)
num = num.to_s
(0..num.length-5).each do |i|
return false unless @primes[num[i,5]]
end
return true
end
def primeDigitSums(n)
total = 0
(10**(n-1)...(10**n)).each do |i|
total += 1 if isChloePrime?(i)
end
return total
end
(0..99999).each do |val|
@primes[val.to_s.rjust(5, "0")] = true if [3,4,5].all? { |n| val.digits.each_cons(n).all? { |set| Prime.prime? set.sum } }
end
解决方案
如果每个非负整数的 3、4 和 5 个数字序列的总和形成一个素数,我认为每个非负整数都是有效的。
构造一组相关的素数
我们需要确定 3 位、4 位和 5 位数字的数字之和是否为素数。因此,最大数不会大于5 * 9
。构造一组这些素数(一组而不是数组来加速查找)很方便。
require 'prime'
require 'set'
primes = Prime.each(5*9).to_set
#=> #<Set: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}>
构造转换哈希
valid1
是一个哈希,其键都是 1 位数字(所有这些数字都是有效的)。键的值0
是所有 1 位数字的数组。因为1-9
值是 2 位数字的数组(所有这些数字都是有效的),这些数字是通过在键上附加一个数字而获得的。总的来说,这些值包括所有 2 位数字。
valid1 = (0..9).each_with_object({}) { |v1,h|
h[v1] = 10.times.map { |i| 10 * v1 + i } }
valid2
是将 2 位数字(全部有效)映射到有效 3 位数字数组的哈希,这些数字是通过将数字附加到 2 位数字而获得的。总的来说,这些值包括所有有效的 3 位数字。所有值都是非空数组。
valid2 = (10..99).each_with_object({}) do |v2,h|
p = 10 * v2
b, a = v2.digits
h[v2] = (0..9).each_with_object([]) { |c,arr|
arr << (p+c) if primes.include?(a+b+c) }
end
请注意,Integer#digits首先返回一个数字为 1 的数组。
valid3
是一个散列,将有效的 3 位数字映射到有效的 4 位数字数组,这些数组是通过将数字附加到键来获得的。总的来说,这些值包括所有有效的 4 位数字。303 个值中有 152 个是空数组。
valid3 = valid2.values.flatten.each_with_object({}) do |v3,h|
p = 10 * v3
c, b, a = v3.digits
h[v3] = (0..9).each_with_object([]) do |d,arr|
t = b+c+d
arr << (p+d) if primes.include?(t) && primes.include?(t+a)
end
end
valid4
是一个哈希,它将有效的 4 位数字映射到有效的 4 位数字数组,这些数组是通过将数字附加到密钥并删除密钥的第一个数字而获得的。valid5.values.flatten.size #=> 218
是有效的 5 位数字的数量。280 个值中有 142 个是空数组。
valid4 = valid3.values.flatten.each_with_object({}) do |v4,h|
p = 10 * v4
d, c, b, a = v4.digits
h[v4] = (0..9).each_with_object([]) do |e,arr|
t = c+d+e
arr << ((p+e) % 10_000) if primes.include?(t) &&
primes.include?(t += b) && primes.include?(t + a)
end
end
我们将这四个散列合并成一个散列@transition
。不再需要以前的哈希值。@transition
有 294 个键。
@transition = [valid1, valid2, valid3, valid4].reduce(:merge)
#=> {0=>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
# 1=>[10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
# ...
# 9=>[90, 91, 92, 93, 94, 95, 96, 97, 98, 99],
# 10=>[101, 102, 104, 106], 11=>[110, 111, 113, 115, 119],
# ...
# 97=>[971, 973, 977], 98=>[980, 982, 986], 99=>[991, 995],
# 101=>[1011], 102=>[1020], 104=>[], 106=>[], 110=>[1101],
# ...
# 902=>[9020], 904=>[], 908=>[], 911=>[9110], 913=>[], 917=>[],
# 1011=>[110], 1020=>[200], 1101=>[], 1110=>[], 1200=>[],
# ...
# 8968=>[], 9020=>[200], 9110=>[], 9200=>[]}
过渡方法
counts
这是每次将用于更新的方法,n
位数,加一。
def next_counts(counts)
counts.each_with_object({}) do |(k,v),new_valid|
@transition[k].each do |new_v|
(new_valid[new_v] = new_valid[new_v].to_i + v) if @transition.key?(k)
end
end
end
prime_digit_sum
方法
def prime_digit_sum(n)
case n
when 1 then 10
when 2 then 90
when 3 then @transition.sum { |k,v| (10..99).cover?(k) ? v.size : 0 }
else
counts = @transition.select { |k,_| (100..999).cover?(k) }.
values.flatten.product([1]).to_h
(n - 4).times { counts = next_counts(counts) }
counts.values.sum % (10**9 + 7)
end
end
请注意,对于n = 4
散列counts
具有有效的 4 位数字的键和全部相等的值1
:
counts = @transition.select { |k,_| (100..999).cover?(k) }.
values.flatten.product([1]).to_h
#=> {1011=>1, 1020=>1, 1101=>1, 1110=>1, 1200=>1, 2003=>1, 2005=>1,
# ...
# 8902=>1, 8920=>1, 8968=>1, 9020=>1, 9110=>1, 9200=>1}
counts.size
#=> 280
如图所示,对于n >= 5
,counts
每次n
递增 1 时都会更新。值的总和等于有效n-digit
数字的数量。
每个有效数字的最后四位数字组成的n
数字是count
的键之一。每个键的值是一个数字数组,其中包含所有有效数字的最后四位数字,这些(n+1)
数字是通过将数字附加到密钥而产生的。
例如,考虑 for 的值,该值counts
如下n = 6
所示。
counts
#=> {1101=>1, 2003=>4, 2005=>4, 300=>1, 302=>1, 304=>1, 308=>1, 320=>1,
# 322=>1, 326=>1, 328=>1, 380=>1, 382=>1, 386=>1, 388=>1, 500=>1,
# 502=>1, 506=>1, 508=>1, 560=>1, 562=>1, 566=>1, 568=>1, 1200=>7,
# 3002=>9, 3020=>4, 3200=>6, 5002=>6, 9200=>4, 200=>9, 1020=>3, 20=>3,
# 5200=>4, 201=>2, 203=>2, 205=>2, 209=>2, 5020=>2, 9020=>1}
考虑密钥2005
并注意
@transition[2005]
#=> [50, 56]
我们看到有4
有效的 6 位数字,其最后四位数字是2005
并且对于这些数字中的每一个,通过将数字和4
相加产生一个有效数字,从而得到最后 5 位数字是和的数字。但是,我们只需要保留最后四位数字和,它们是数字和。因此,在重新计算--call it -- 时,我们同时添加和。(for )的其他键可能具有包含and的值,因此它们也会对and有贡献。0
6
20050
20056
0050
0056
50
56
counts
n = 7
counts7
4
counts7[50]
counts7[56]
k
counts
n=6
@transition[k]
50
56
counts7[50]
counts7[50]
选择性结果
让我们试试它的各种值n
puts "digits nbr valid* seconds"
[1, 2, 3, 4, 5, 6, 20, 50, 100, 1_000, 10_000, 40_000].each do |n|
print "%6d" % n
t = Time.now
print "%11d" % prime_digit_sum(n)
puts "%10f" % (Time.now-t).round(4)
end
puts "\n* modulo (10^9+7)"
digits nbr valid* seconds
1 10 0.000000
2 90 0.000000
3 303 0.000200
4 280 0.002200
5 218 0.000400
6 95 0.000400
20 18044 0.000800
50 215420656 0.001400
100 518502061 0.002700
1000 853799949 0.046100
10000 590948890 0.474200
40000 776929051 2.531600
推荐阅读
- python - 如何将以太坊地址转换为公钥
- python - 使用额外共享变量加入和过滤两个重叠 DataFrame 的更快方法
- android - 靠近时检测信标,iOS 和 Android 应用程序
- speech-synthesis - SpeechSynthesisUtterance onmark - 工作示例
- mysql - 选择同一张表的选项 - MySQL
- python - 使用 python 重命名文件时出现问题,某些字符拒绝更改。(可能是更改编码的问题)
- influxdb - InfluxDB:分组超过1天时开始时间错误
- excel - 嵌套的直到循环如何工作?
- reactjs - 在 AsyncStorage 或 redux 中存储全局数据的最佳方式?
- angular - 按用户过滤mongodb数据