Попытка написать сценарий программы, которая перечисляет числа, цифры которых в сумме дают простое число в Python. Как мне исправить ошибку переполнения?

def isPrime(num):
    s=0
    for j in range (1, num):
        if(num%j==0):
            s=s+1
            if(s>1):
                break
    return(s)

a = 10**20;
b = 10**400;
for i in xrange(a, b):
        if(isPrime(i)==1 and isPrime(sum(int(x) for x in str(i)))==1):
            print('Sum of all digits of', i, 'is', sum(int(x) for x in str(i)))

Моя цель - вывести все числа в пределах 10 ^ 20 и 10 ^ 400, цифры которых в сумме дают простое число, чтобы ответить на вопрос: «Сколько существует целых чисел в диапазоне [10 ^ 20, 10 ^ 400], таких что сумма их цифр - простое число? "

Во время поиска в Google я прочитал, что диапазон будет переполнен, и что xrange будет более эффективным. Когда использовался xrange, возникала ошибка «OverflowError: Python int слишком большой для преобразования в C long;» имеет место.

Как я могу вывести ответ без ошибок?


python sum overflow digits primes
person NyonX    schedule 20.05.2017    source источник
comment
Вам нужно найти другой способ сделать это или купить себе вечность ...   -  person Thierry Lathuille    schedule 20.05.2017
comment
Здесь вам понадобится серьезное количество оперативной памяти, а не такой простой алгоритм, как этот.   -  person Stavros Avramidis    schedule 20.05.2017
comment
Вам нужно больше взглянуть на перестановки и комбинации. Вас не интересует порядок цифр, а только их сумма. Число размером 10 ^ 20 будет состоять из 20 цифр. Рассматривайте их как набор списков отдельных цифр: от (0, 0, 0, ... 0, 0) до (9, 9, 9, ... 9, 9). Когда у вас есть список, который в сумме составляет простое число, определите, сколько существует перестановок этого списка.   -  person rossum    schedule 24.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

Был задан вопрос, похожий на этот для python 2.x, кажется: Обработка больших чисел в коде это может помочь для меньшего числа ...

В целом ответ через Quora довольно информативен: https://www.quora.com/How-large-can-Python-handle-big-number, как говорили другие, это будет зависеть от того, сколько памяти у вас доступно.

Из статьи на Quora:

Реальный лимит зависит от объема памяти, к которому Python имеет доступ. Если бы в его распоряжении был, скажем, 1 ГБ, это составило бы примерно 80000000008000000000 бит. Таким образом, это позволило бы иметь числа вплоть до 2800000000028000000000. Если бы мы могли каким-то образом использовать 600+ ТиБ памяти ЦП суперкомпьютера Titan специально для вычисления чисел, мы могли бы достичь примерно 22522252. Это много.

person Jeremy    schedule 20.05.2017