确定素数有序对 (p, q) 的数量，使得 N = p^2+q^3 使得从 0 到 9 的每个数字恰好出现一次

Question

我必须编写一个程序来确定素数（p，q）的有序对的数量，这样当N = p ^ 2 + q ^ 3写成十进制时，从0到9的每个数字只出现一次（没有前导零）。

我想使用埃拉托色尼筛的变体，正如它所解释的那样here，但是它也提到筛子仅适用于数字N，这样N小于一千万，但根据问题的陈述，每个N位于至少一亿个数字，因为每个数字只出现一次并且没有前导零，但除了这个之外我没有任何其他想法，所以任何帮助将不胜感激。

Answer 1

利用这样一个事实：您可以立方并仍形成潜在有效数字的最大素数是 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 by converting to a set
      s = combined_val.to_s
      if s.split('').to_set.size == 10
        count += 1
        puts "val: #{s} = #{prime_to_square}^2 + #{prime_to_cube}^3, count: #{count}"
      end
    end
  end
end

结果：

> 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