** 알고리즘 오답노트 01

소수 구하기

• 틀린 부분 : 연산 횟수를 더 줄일 수 있었는데 그렇지 못했음.
• 틀린 이유 : 소수를 구하는 방식에 이런게 있는줄 미처 생각 못했다...

# 어떤 자연수의 제곱근보다 작은 소수들로 나누어떨어지지 않으면 그 자연수는 소수이다.
# 예를 들어 17은 17의 제곱근인 4.xxx 보다 작은 소수들 2,3로 나누어떨어지지 않으므로 17은 소수이다.
# 반면 18은 2,3 중 2,3으로 나누어떨어지므로 소수가 아니다.

number = 20
prime_list = []

for n in range(2, number + 1):
  for i in prime_list:
    if i * i >= n:
    # 제곱근보다 커져버린 수로는 나눠봤자 의미 없기때문에 여기까지 온 이상 이미 소수인걸 증명한것이고 break 해버린다.
      prime_list.append(n)
      break
    elif n % i == 0:
      break
  else:
    prime_list.append(n)

print(prime_list)

위 코드는 소수인지 아닌지를 구별하는데 좋고, 아래 코드(에라토스테네스의 체)는 어떤 수보다 작은 소수의 리스트를 뽑아내는데 좋다.

def prime_list(n):
  seive = [True] * n
  m = int(n ** 0.5)
  for i in range(2, m+1):
    if seive[i] == True:
      for j in range(i*2, n, i):
        seive[j] = False
  return [i for i in range(2, n) if seive[i]==True]
  
print(prime_list(10))
# [2, 3, 5, 7]