[0818] 소수 나열하기

문제

정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.

(소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)

# 20이 입력된다면, 아래와 같이 반환해야 합니다!
[2, 3, 5, 7, 11, 13, 17, 19]

코드

def find_prime_list_under_number(number):
    prime_list = []
    for num in range(2, number+1):
      for i in prime_list:
        if num % i == 0 and i * i <= num:
          break
      else:
        prime_list.append(num)
          
    return prime_list

시간 복잡도

• 코드의 시간 복잡도는 number의 길이 N과 prime_list의 길이인 N만큼을 곱한 𝑶(𝑵²)이 될 것 같다고 생각한다.