2보다 큰 자연수 중에 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수를 소수라고 말합니다.
보통 요즘 코딩테스트 문제에 단골주제로 많이 나오니 이번에 한번 알아보고자 합니다.
그리고 참고로 소수가 왜 중요한지 그리고 어디다가 사용하는지에 대해서는 다음 링크를 참고해주시고..
https://www.joongang.co.kr/article/22283770#home
https://www.hani.co.kr/arti/society/schooling/164651.html
소수를 구하는 방법에는 보통 두가지 방법이 있습니다.
첫번째는 정말 소수 그자체를 구하기 위해 소인수분해하는 방법이 있고...
두번째는 "아라토스테네스의 체"라고 하는 고대 그리스 수학자가 고안한 방식이 있습니다. (고대 사람인대 저보다 낫네요;;)
첫번째 방식의 경우는 소수의 정의대로 구현하는 방식은 다음과 같습니다.
import time
n = 10000
start_time = time.time()
for i in range(2, n+1):
result = True
for j in range(2, i):
if i % j == 0:
result = False
if result:
print(i, end=" ")
end_time = time.time()
print("\n")
print("일반시간", end_time - start_time)
소요시간이 대략 0.085초 걸렸네요.
그럼 두번째 방식인 "아라토스테네스의 체"방식을 알아보기 전에 어떤 알고리즘으로 동작되는지 아래 그림을 참고해보시면 좋을꺼 같습니다.
이 방식을 코드로 구현하면 다음과 같습니다.
import time
n = 1000
start_time = time.time()
a = [False,False] + [True]*(n-1)
result=[]
for i in range(2, n+1):
if a[i]:
result.append(i)
for s in range(2*i, n+1, i):
a[s] = False
print(result)
end_time = time.time()
print("\n")
print("에리토스테네스의 체 시간", end_time - start_time)
실행된 소요시간은 0.00098 초 걸렸네요.
역시 일반적인 방법보다는 알고리즘을 사용해서 구현한 방식이 훨씬 빠르다는 것을 알 수 있습니다.
이러한 차이는 숫자가 늘어날수록(연산할게 많아질 수록) 그 진가가 발휘됩니다.
그러니 열씸히 공부해야겠지요;;;;;
리스트의 인덱스가 필요하다면, enumerate (0) | 2021.03.20 |
---|---|
파이썬 ipaddress 라이브러리 (0) | 2021.03.18 |
파이썬 config 파일의 민감정보 분리방법 (0) | 2021.03.18 |
명령어 한줄로 웹서버 실행하기 (0) | 2021.03.08 |
댓글 영역