Как получить простую коллекцию в пределах 2 ^ 63 - 1 в Python - PullRequest
Новая
       4

Как получить простую коллекцию в пределах 2 ^ 63 - 1 в Python

0 голосов
/ 16 ноября 2018

Я хочу получить простое число, установленное в Python на 2 ^ 63 - 1, я видел следующий код в Интернете: 

limit = 2**63 - 2
p = [True] * (limit + 1)
# p = bitarray(limit + 1)
p[0] = p[1] = False
for i in range(2, int(math.sqrt(limit) + 1)):
    if p[i]:
        for j in range(i * i, limit + 1, i):
            p[j] = False
prime = [i for i in range(limit + 1) if p[i]]
print(prime)

Но когда я запускаю эту программу, компилятор жалуется, чтоcan not fit 'int' into an index-sized integer.Я пытался решить проблему с bitarray, но индекс массива все еще слишком велик.

Ответы [ 3 ]

0 голосов
/ 16 ноября 2018

если у вас есть какой-то генератор primes(), вы можете сделать это: 

is_prime_var = 0

MAX = 1 << 5
last_p = 0
for p in primes():
    if p > MAX:
        break
    print(p, p-last_p)
    is_prime_var <<= (p - last_p)
    is_prime_var |= 1
    last_p = p
is_prime_var <<= (MAX - last_p - 1)

теперь местоположения простых чисел сохраняются (в обратном порядке) в целых числах is_prime_var.

тогда выражение (is_prime >> (MAX-n-1)) & 1 будет 1, если n является простым;0 в противном случае: 

def is_prime(n):
    return bool((is_prime_var >> (MAX-n-1)) & 1)

вы можете использовать primes() из этот превосходный ответ в качестве основного генератора.

thers также этот мой ответ о быстром и эффективном по отношению к памяти сите из эратосфена.также может быть интересно.

0 голосов
/ 16 ноября 2018

Вы можете использовать следующий код. Он использует Сито Эратосфена в сочетании с функцией генератора, чтобы уменьшить использование памяти этим алгоритмом. Кроме того, используется менее общеизвестный факт, что каждое простое число> 4 может быть записано как 6 * n ± 1. 

import math

limit = 2 ** 63 - 1

def isPrim(n, belowPrims):
    limit = int(math.sqrt(n))
    for prim in belowPrims:
        if prim > limit: break
        if n % prim == 0: return False 
    return True

def calcPrims():
    yield 2
    yield 3
    toTest, nextN = [], 6
    while True:
        p1 = nextN - 1
        if isPrim(p1, toTest):
            yield p1
            toTest.append(p1)
        p2 = nextN + 1
        if isPrim(p2, toTest):
            yield p2
            toTest.append(p2)
        nextN += 6

for prim in calcPrims():
    if prim > limit:
        break
    print(prim)

Редактировать

Эта ссылка здесь https://primes.utm.edu/notes/faq/six.html кратко объясняет, почему каждый номер прим может быть записан в виде 6 * n ± 1.

0 голосов
/ 16 ноября 2018

Вы можете использовать sympy: 

import sympy

print(list(sympy.primerange(0,2**63-1)))

, но если 2 ^ 63 достаточно велико, это займет некоторое время.

...