파이썬으로 소수 리스트를 만드는데

조회수 48회
import math
import pickle


def prime_list(n):
    sieve = [True] * (n+1) # true: prime, false: not prime. default: true

    for i in range(2, int(math.sqrt(n))+1):
        if sieve[i] == True:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    return [i for i in range(2,n+1) if sieve[i] == True]



list1 = prime_list(1000000000)

with open("prime_10^9.pickle","wb") as fw:
    pickle.dump(list1, fw)

에라토스테네스 체로 소수 리스트를 만드는데 108 이하의 소수 목록은 만들어지는데 109 부터는 메모리 오류가 나오네요. 혹시 어떻게 해야 될까요? 리스트 대신에 다른 자료형을 쓰면 될까요? 참고로 numpy 같은 모듈을 사용할 수가 없습니다.

1 답변

    1. 파이썬의 불리언이 어떤 형으로 만들어지는지 잘 모르겠는데, 리얼 1비트가 아니고 int 형이라고 하면, True N 개가 32비트 int N 개랑 메모리 용량을 같을 거에요. 그러니까, 각 배열의 원소를 0xFFFF 로 초기화하고, 원소 하나당 32개의 True 를 비트로 세워서, 비트연산을 통해서, 32배의 메모리를 절약할 수 있죠. 이거 할려면 비트연산 잘 해야 하고요.

    2. 이렇게 여러가지 방법으로 에라스토테네스의 방법을 해 보고, 그 이상의 소수들을 구하고 싶다고 하면...

    primes = get_primes_erasto(N)
    
    candidate = smallest_odd_number_greater_than(N)
    while candidate < VERYVERYBIGN:
      for prime in primes:
        if candidate % prime:
          break
        if candidate < prime*prime:
          primes.append(candidate)
          break
    
      candidate += 2
    

    이렇게 하는 방법도 있을 거에요. 효율적인지는 모르겠어요.

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.