오늘도 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}')

---

숫자가 너무 많아서 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 번으로 크게 줄었고, 알고리즘을 개선함에 따라 계산속도가 빨라졌다.

알고리즘이 중요한 것은 알겠는데, 내가 아직 식을 만드는데 다양하게 생각하지 못하는 것이 문제인 것 같다.

꾸준히 공부해서 코드를 어떻게하면 더 좋게 만들 수 있을지 방향을 잡아가는 것이 중요한 것 같다 😥