小于或等于N的两个数对的计数数，使该对数的位数之和为素数

Question

null

我可以想到蛮力方法。其中我需要放两个从1到N的循环，计算每个x和y对的数字和，并检查它是否是素数。但它不是一个最优解，因为N的范围为10^50。

Answer 1

我一直在尝试这个问题--我花了几次努力才明白这个问题。我想在放弃之前把我学到的东西写下来，然后转向更容易的事情！

首先，我对@Shiva解决方案的返工，它能更快地产生正确的输出：

import sys
from functools import lru_cache

def sum_of_digits(number):
    summation = 0

    while number > 0:
        summation += number % 10
        number //= 10

    return summation

@lru_cache()
def is_prime(number):
    if number < 2:
        return False

    if number % 2 == 0:
        return number == 2

    divisor = 3

    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 2

    return True

maximum = int(sys.argv[1])

count = 0

for i in range(maximum + 1):
    sum_i = sum_of_digits(i)

    for j in range(i, maximum + 1):
        if is_prime(sum_i + sum_of_digits(j)):
            count += 1

print(count)

我在下面用这个作为速度和准确性的基准。

import sys
from math import ceil
from collections import defaultdict

VERBOSE = False

def sum_of_digits(number):
    summation = 0

    while number:
        summation += number % 10
        number //= 10

    return summation

def sieve_primes(n): 
    sieve = [False, False] + [True] * (n - 1)

    divisor = 2

    while divisor * divisor <= n: 
        if sieve[divisor]: 
            for i in range(divisor * divisor, n + 1, divisor): 
                sieve[i] = False
        divisor += 1

    return [number for number in range(2, n + 1) if sieve[number]]

power = int(sys.argv[1])  # testing up to 10 ** power

maximum_sum_of_digits = 18 * power
primes_subset = sieve_primes(maximum_sum_of_digits)

sums_of_digits = defaultdict(int)
for i in range(10 ** power + 1):
    sums_of_digits[sum_of_digits(i)] += 1

if VERBOSE:
    print('maximum sum of digits:', maximum_sum_of_digits)
    print('maximum prime:', primes_subset[-1])
    print('number of primes:', len(primes_subset))
    print('digit sums cached', len(sums_of_digits))

primes_subset = set(primes_subset)

count = 0

for i in sums_of_digits:
    sum_i = sums_of_digits[i]

    for j in sums_of_digits:
        if i + j in primes_subset:
            count += sum_i * sums_of_digits[j]

print(ceil((count + 2) / 2))  # hack to help adjust between duples and no duples count; sigh

        @Shiva reworked            My Attempt
          exact    secs        approx    secs
10^1         24    0.03            24    0.03
10^2       1544    0.04          1544    0.04
10^3     125030    0.49        125029    0.04
10^4   12396120   51.98      12396119    0.05
10^5 1186605815 6223.28    1186605813    0.14
10^6                     113305753201    1.15
10^7                   11465095351914   12.36
10^8                 1120740901676507  137.37
10^9               105887235290733264 1626.87