我必须编写一个程序,可以确定素数 (p, q) 的有序对的数量,这样当 N = p^2+q^3 以十进制书写时,从 0 到 9 的每个数字只出现一次(没有前导零)。
我想到使用埃拉托斯特尼筛的变体,正如它所解释的那样here https://www.geeksforgeeks.org/sieve-of-eratosthenes/,然而,它也提到,筛子仅适用于数字 N,使得 N 小于一千万,但根据问题的陈述,每个 N 至少是一亿,因为每个数字只出现一次并且没有前导零,但除了这个之外我没有任何其他想法,所以任何帮助将不胜感激。
利用以下事实:您可以立方并仍形成潜在有效数字的最大质数是 2143。
Ruby 代码(如果不使用 Ruby,请阅读伪代码):
require 'prime'
def f()
# Determine the max & min numbers that can be made with 10 distinct digits and no leading zeroes
max_num = 9_876_543_210
min_num = 1_023_456_789
# Find the largest prime having a cube <= max_num
max_prime_to_cube = 2143
count = 0
# Cube every prime up to 2143
Prime.each do |prime_to_cube|
return count if prime_to_cube > max_prime_to_cube
cubed_val = prime_to_cube ** 3
# Try adding the square of every prime until we exceed the maximum valid number
Prime.each do |prime_to_square|
squared_val = prime_to_square ** 2
combined_val = squared_val + cubed_val
next if combined_val < min_num
break if combined_val > max_num
# Check if all digits are unique
if has_each_digit_once(combined_val)
count += 1
puts "val: #{combined_val} = #{prime_to_square}^2 + #{prime_to_cube}^3, count: #{count}"
end
end
end
end
# Check each digit, setting bits of check_int where the i'th bit represents digit i
def has_each_digit_once(val_to_check)
check_int = 0
10.times do
check_bit = 1 << (val_to_check % 10)
# Exit early if we see a digit for the second time
return false if check_bit & check_int > 0
check_int |= check_bit
val_to_check /= 10
end
return check_int == 1023
end
Results:
> f
val: 1328675409 = 36451^2 + 2^3, count: 1
val: 1478325609 = 38449^2 + 2^3, count: 2
val: 3085469217 = 55547^2 + 2^3, count: 3
val: 3507126849 = 59221^2 + 2^3, count: 4
...
val: 9682357410 = 5689^2 + 2129^3, count: 1267
val: 9837162450 = 13681^2 + 2129^3, count: 1268
val: 9814362750 = 523^2 + 2141^3, count: 1269
val: 9815674302 = 1259^2 + 2141^3, count: 1270
=> 1270
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)