파이썬으로 소수 리스트를 만드는데
조회수 852회
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비트가 아니고 int 형이라고 하면, True N 개가 32비트 int N 개랑 메모리 용량을 같을 거에요. 그러니까, 각 배열의 원소를 0xFFFF 로 초기화하고, 원소 하나당 32개의 True 를 비트로 세워서, 비트연산을 통해서, 32배의 메모리를 절약할 수 있죠. 이거 할려면 비트연산 잘 해야 하고요.
이렇게 여러가지 방법으로 에라스토테네스의 방법을 해 보고, 그 이상의 소수들을 구하고 싶다고 하면...
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이렇게 하는 방법도 있을 거에요. 효율적인지는 모르겠어요.
댓글 입력