# 10. TIL
오늘도 Do it! 알고리즘 파이썬편을 공부했습니다. 😗
1,000 이하 소수 나열하기
# 1,000 이하 소수 나열하기 (1)
count = 0
for n in range(2, 1001):
for i in range(2, n):
count += 1
if n % i == 0: # 나누어 떨어지면 소수가 아님
break
else:
print(n)
print(f'나눈 횟수 : {count}')
# 1,000 이하 소수 나열하기 (1)
count = 0
for n in range(2, 1001):
for i in range(2, n):
count += 1
if n % i == 0: # 나누어 떨어지면 소수가 아님
break
else:
print(n)
print(f'나눈 횟수 : {count}')
숫자가 너무 많아서 n값을 2씩 증가시켜 3, 5, 7, 9...., 999로 홀수의 값을 생성한다. 4, 6, 8 등은 소수가 아니기 때문이다.
# 1000 이하 소수를 나열하기 (2)
count = 0
fd_num = 0 # 이미 찾은 소수의 개수
prime = [None] * 500 # 배열에 소수를 저장(짝수는 소수가 아니므로 전체 1000개 중 절반에 모든 소수를 넣을 수 있기 때문에 원소를 500으로 지정)
prime[fd_num] = 2 # 2는 소수라 초깃값 지정
fd_num += 1
for n in range(3, 1001, 2):
for i in range(1, fd_num):
count += 1
if n % prime[i] == 0:
break
else: # 나누어지지 않았으니 소수를 배열에 등록
prime[fd_num] = n
fd_num += 1
for i in range(fd_num):
print(prime[i])
print(f'나눗셈을 실행한 횟수: {count}')
'n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는 조건을 만족하면
소수
이다.' 라는 조건식을 이용
# 1000 이하의 소수를 나열하기 (3)
count = 0
fd_num = 0
prime = [None] * 500
prime[fd_num] = 2 # 2는 소수
fd_num += 1
prime[fd_num] = 3 # 3은 소수
fd_num += 1
for n in range(5, 1001, 2): # 그 다음 소수는 5이며 홀수만을 대상으로 범위 지정
i = 1
while prime[i] * prime[i] <= n:
count += 2
if n % prime[i] == 0:
break
i += 1
else:
prime[fd_num] = n
fd_num += 1
count += 1
for i in range(fd_num):
print(prime[i])
print(f'곱셉과 나눗셈을 실행한 횟수: {count}')
😱 알고리즘의 중요성
계산 횟수가 78022 -> 14622 -> 3774 번으로 크게 줄었고, 알고리즘을 개선함에 따라 계산속도가 빨라졌다.
알고리즘이 중요한 것은 알겠는데, 내가 아직 식을 만드는데 다양하게 생각하지 못하는 것이 문제인 것 같다.
꾸준히 공부해서 코드를 어떻게하면 더 좋게 만들 수 있을지 방향을 잡아가는 것이 중요한 것 같다 😥
Author And Source
이 문제에 관하여(# 10. TIL), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wlgns410/10.-TIL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)