SCC Algorithm 1주차 HW1

Homework 1

정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
(소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)

내가 처음 풀었던 풀이

def find_prime_list_under_number(number):
    prime_list = []
    if number <= 0:
        return "양의 정수를 입력하여 주세요."
    elif number == 1:
        return "1은 소수가 아닙니다."
    else:
        for num in range(2, number+1):   # 2, 3, 4, 5, 6, ... 9
            prime_list.append(num)
            for count in range(2, num):     # 3부터 시작됨 (2는 어차피 소수니까 자연스럽게 포함)
                result = num % count
                if result == 0:
                    prime_list.pop(prime_list.index(num))
                    break
                else:
                    continue
    return prime_list

• 해당 풀이의 문제점 : for 반복문의 이중 중첩으로 인하여 시간복잡도가 N^2이 됨

해설을 보고 다시 생각한 풀이

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

• 핵심 : n이 소수가 아니면 2이상 √n이하의 약수를 가진다는 성질을 이용
  주어진 자연수 n이 소수이기 위한 필요충분 조건은 n이 n의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다는 사실이다.
  수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문입니다.

• 성질 증명 : n은 소수가 아니므로 두 자연수 p,q(2<=p<=q)의 곱으로 나타낼 수 있다.
  n =pq이고, p는 √n보다 같거나 작다.
  그렇지 않다면, n=pq > √n * √n = n 이 되어 모순이다.

• 결과적으로 해당 풀이의 시간 복잡도는 n√n이 되므로 첫 번째 풀이의 시간복잡도 N^2보다 연산 횟수가 적으므로 효율적이라고 볼 수 있다.

모든 알고리즘은 개선할 수 있다.라는 생각을 마음 속에 지니기!

문제를 어떻게 하면 효율적으로 풀 수 있을지 항상 고민하자.