스파르탄 365 1주차

1. 문제 링크

https://online.spartacodingclub.kr/enrolleds/606a6494ca5c2e219f9ca31e/ehomeworks/606a6494ca5c2e219f9ca34f

2. 풀이 생각

• 소수: 자기 자신과 1 외에는 아무것도 나눌 수 없다.
• 1차 개선: 2 ~ number + 1 까지 모두 검사 -> 2, 3 안된다면 6도 당연히 X -> 2 ~ n-1 까지 생각.
• 2차 개선: 소수 -> N이 N의 제곱근보다 크지 않은 어떤 소수로도 나누어지지 X, 나누었을 때 몫과 나누는 수 둘 중 반드시 N의 제곱근 이하이다.( i * i <= n)

3. 풀이

input = 20

# 소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다.
def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i*i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

4. 소감

기본적인 for, if 사용법을 다시 생각하게 되었고 python을 통해서 코딩테스트에 합격한다면 정말 기쁠 것 같다 :)