[백준] - 소수 나열하기(1929)/파이썬

문제 링크

https://www.acmicpc.net/problem/1929

문제

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

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

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

---

 

정답 풀이

1번 풀이

풀이

1. 소수를 넣을 배열 선언
2. 2 ~ number 까지의 숫자들이 n 에 들어가는 것을 반복
3. 2 ~ n-1 까지 i 에 들어가는 것을 반복
4. n 이 i 로 나눠떨지면 소수가 아님으로 반복분 탈출
5. 2 ~ n-1 까지 n 이 나눠 떨어지지 않으면 배열에 추가

정답 코드

input = 20

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

result = find_prime_list_under_number(input)
print(result)

2번 풀이

풀이

• n 이 19 일 경우 2와 3으로 나누어 떨어지지 않는 경우 6으로도 나누어 떨어지지 않게 됨 즉, 2와 3으로 나누어 떨어지면 6으로 나누어 떨어짐
• 1번 풀이의 n 보다 작은 수 대신 → n 보다 작은 소수들로 비교하면 됨

정답 코드

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:
                break
        else:
            prime_list.append(n)
    return prime_list

result = find_prime_list_under_number(input)
print(result)

3번 풀이

풀이

• 소수이기 위한 필요 충분 조건 : N의 제곱근 보다 크지 않은 어떤 소수로도 나눠 떨어지지 않는다
• 예를 들어
  • 18 의 약수는 1,2,3,6,9,18
  • 18 의 제곱근 → 4<루트 18<5 이므로 4.xxx
  • 4.xxx 보다 작은 소수 2, 3 으로만 검사해주면 됨
• i * i ≤ n 일 때까지만 비교

정답 코드

input = 20

def find_prime_list_under_number(number):
    prime_list = []

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

    return prime_list

result = find_prime_list_under_number(input)
print(result)

---

문제를 풀고 알게 된 개념 및 소감

• 소수 : 자기 자신과 1 외 에는 아무것도 나눌 수 없다.
• for-else
  • 입력된 배열에 특정 값이 존재하느냐 아니냐에 따라서 행동을 하고 싶은 경우 사용
  • for 문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행 됐을 경우 else 문이 실행 ㅋ

for x in [1,2,3,4]
	print(x)
else:
	print("완료")

출력
1
2
3
4
완