•
문제 설명
말그대로 2개의 숫자 M, N 을 받은 후, 해당 숫자 범위 중 소수(prime number)를 찾아 구하는 문제이다.
소수란?
1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.
즉, 1은 소수가 아니다.
•
풀이 방법
1.
2 ~ 까지 나눠지는 값이 있는지 확인 [ 시간 복잡도 : ]
2.
2 ~ 까지 나눠지는 값이 있는지 확인 [ 시간 복잡도 : ]
3.
2 ~ 까지 나눠지는 값이 있는지 확인 [ 시간 복잡도 : ]
당연히 3번째 방법으로 하는 것이 가장 짧은 시간에 가능하다.
처음엔 1번 방법으로 했지만, 시간 제한으로 인한 실패를 맛봤기 때문이다.. ㅠㅠ
•
성공 코드
•
코드 설명
1은 소수가 아니기 때문에 인자 n 값이 1일 경우 소수가 아니므로 False 반환
...(생략)
def is_prime(n):
if n == 1:
return False
...(생략)
Python
복사
2 ~ 까지 숫자를 확인 후, 약수가 1개라도 존재한다면 소수가 아니므로 False 반환
...(생략)
# 2 ~ N 제곱근(실수 연산을 막기 위해 int형으로 변환) 까지
for i in range(2,int(math.sqrt(n)) + 1):
if n % i == 0:
return False
...(생략)
Python
복사
출처
