import math
def solution(n):
answer = 0
for i in range(2,n+1):
if primenumber(i):
answer+=1
return answer
def primenumber(x):
for i in range(2,x):
if x % i == 0:
return False
return True
이렇게 써서 제출했는데 시간초과가 났다.
import math
def solution(n):
answer = 0
for i in range(2,n+1):
if primenumber(i):
answer+=1
return answer
def primenumber(x):
# 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
return True
반복문의 범위 설정 시에 입력받은 숫자까지 약수의 여부를 검증할 필요가 없다. 입력받은 숫자의 제곱근까지만 약수의 여부를 검증하면 시간초과를 막을 수 있다.
이렇게 유용한 정보를 공유해주셔서 감사합니다.