서론 (잡설)
?????????????????
골드바흐의 추측 문제가 재채점 되면서 원래 풀었던 문제가 오답처리되고 말았다.
기존 알고리즘으로는 더이상 풀지 못하게 되었으므로, 소수를 찾는 새알고리즘을 배우는 겸사겸사 몰랐던 파이썬 문법도 배워보자.
소수 찾기
기존 방법
def get_prime():
for num in range(2, 1001):
for i in range(2, math.isqrt(num)+1):
if num % i == 0:
prime_list[num] = False
break
if __name__=="__main__":
MAX_NUM = 1000000
prime_list = [True] * (MAX_NUM+1)
get_prime()
for i in range(2, 1001):
if prime_list[i]:
for j in range(i+i, MAX_NUM+1, i):
prime_list[j] = False에라토스테네스의 체를 이용한 기본적인 방식이다.
에라토스테네스의 체를 간단히 설명하자면 1,000,001이 소수인지 아닌지 알기 위해서는 sqrt(1,000,001) ≒ 1,000까지의 수만 검사하면 된다는 것이다.
따라서 최대값이 1,000,000이므로, 1000까지의 소수는 일일히 검사해서 리스트로 만든 뒤, 1000을 넘는 수는 모두 2~1000 중 소수인 값만을 곱해서 소수 리스트를 만들었다.
단점
2부터 1,000,000까지의 인덱스가 모두 리스트에 들어있기 때문에, 일일이 탐색하면서 소수인지 아닌지 확인해야 한다.
-> 시간초과의 주범
과제 : for문에서 소수만 쏙쏙 빼올 수 있도록 해야한다.
새로운 방법
MAX_NUM = 1000000
prime_list = list(range(MAX_NUM+1))
for i in range(2, 1001):
if prime_list[i]:
prime_list[i+i::i] = [0] * len(prime_list[i+i::i])
prime_list = list(filter(None, prime_list[2:]))
prime_set = set(prime_list)코드 설명
2에서 1000까지 소수를 구할 필요가 없다!
101을 예를들어 생각하면 sqrt(101) ≒ 10 이므로 10까지의 수로만 나누어 떨어지지 않으면 소수로 판정할 수있다.
그리고 sqrt(10) = 3.xx 이므로 3까지의 수로만 나누어 떨어지지 않으면 소수로 판정할 수 있다.
즉, 그냥 처음부터 2를 제외한 2의 배수를 전부 소수가 아닌 것으로 처리하면 4이하의 남은 수는 모두 소수라고 할 수 있다.
- 확실한 소수 : [2, 3]
다음 소수인 3부터 3의 배수를 전부 소수가 아닌 것으로 처리하면 9이하의 남은 수는 모두 소수라고 할 수 있다.
- 확실한 소수 : [2, 3, 5, 7]
이런식으로 확실한 소수를 남기면서 진행하면 약수 경우를 따지면서 일일히 소수를 구하지 않아도 된다.
리스트 슬라이싱
list = [0, 0, 0, 0, 0, 0, 0]
list[::2] = [1, 2, 3, 4]
print(list)
>>> [1, 0, 2, 0, 3, 0, 4]파이썬의 리스트 슬라이싱은 이런 문법도 가능하다.
2중 for loop를 일일히 돌면서 처리할 필요 없이 for loop 하나로 같은 동작이 가능하다.
filter None
filter에 함수 대신 None을 넣으면 False에 해당하는 값을 모두 지워준다. (0, False, None 등등)
즉 소수가 아닌 값을 0으로 만들어 놓고, filter(none)에 넣으면 해당 값이 사라지게 된다.
이를 통해 소수만 남은 리스트를 얻을 수 있다.
바다코끼리 연산자 (Walrus operator)
:= : 파이썬 3.8에서 추가된 연산자로 값을 할당함과 동시에 해당 값을 반환하는 연산자이다.
while문과 함께 사용하면 궁합이 좋다.
print(a := 5)
>>> 5바다코끼리 연산자가 없었다면 이렇게 써야한다.
while True:
n = int(input())
if not n:
break코멘트
재채점 덕분에 몰랐던 것을 많이 배울 수 있었다.
이제 소수 관련문제는 진짜로 무섭지 않아!!!
평소에 while True를 자주쓰는 편인데, 바다코끼리와 함께라면 보다 압축된 코드를 쓸 수 있을 것 같다.
filter None도 기억해두자.
