def solution(n):
answer, count = 0, 0
for num in range(1, n+1):
for num2 in range(1, n+1):
if num % num2 == 0:
count += 1
else:
pass
if count == 2:
answer += 1
count = 0
return answer
print(solution(10)) # 4
print(solution(5)) # 3
count 위치를 앞으로 땡겨주니 정답이 잘 나온다
근데 팀원분이 이런 문제는 시간복잡도에 따라 점수가 갈린다고 하셔서 줄일 수 있는 방법을 찾아봤는데
일단 소수 판별할 때 나누는 값인 num2를 n+1만큼 돌려줄 필요가 없다 num+1만큼만 돌려주면 된다
근데 또 찾아보니까 다 돌릴 필요도 없고 num의 제곱근을 찾아서 제곱근보다 작은 수 중에 0으로 나누어 떨어지는 값이 없으면 소수인 거라고 할 수 있다고 한다
그리고 1은 이미 모든 수로 나눠지니까 1을 나누는 수와 나눠지는 수로 둘 필요도 없다고 한다
아 그리고 제한 조건을 보니 이미 n은 2 이상 1000000 이하의 자연수라고 하네
import math
def solution(n):
answer, count = 0, 0
for num in range(2, n+1):
for num2 in range(2, int(math.sqrt(num))+1):
if num % num2 == 0:
count += 1
if count == 0:
answer += 1
count = 0
return answer
print(solution(10)) # 4
print(solution(5)) # 3
그래서 이런 식으로 바꿔줬는데 프로그래머스에 정답을 채점하려고 하니 테스트 11에서 시간초과가 나온다
역시 for문이 2개 있어서 그런가..
소수 판별하는 함수와 카운팅하는 함수로 나눠야겠다는 생각이 들었다
검색하다가 에라토스테네스의 체라는 걸 알게 됐는데 어떻게 활용해야 할지 모르겠어서 일단 제껴둠..
함수를 나눠도 어쨌든 for문은 2번 돌아가는데 왜인지 함수를 둘로 나누니까 테스트를 통과했다
심지어 이제까지 얻은 점수 중에 제일 높은 점수를 얻었다!위에 함수 하나에 for문 2개 겹쳐 쓴 풀이 실행 결과아래 완성된 코드 실행 결과
시간이 좀 걸리긴 했지만 그래도 시간초과는 하지 않아서 테스트가 통과됐다..ㅎㅎ
<완성된 코드>
import math
def is_prime_number(number):
for i in range(2, int(math.sqrt(number))+1):
if number % i == 0:
return 0
return 1
def solution(n):
answer = 0
for num in range(2, n+1):
answer += is_prime_number(num)
return answer
print(solution(10)) # 4
print(solution(5)) # 3
<다른 사람 풀이>
- 천재풀이1
def solution(n):
num=set(range(2,n+1))
for i in range(2,n+1):
if i in num:
num-=set(range(2*i,n+1,i))
return len(num)
def solution(n):
num = set(range(2, n+1))
print("시작 ", num)
for i in range(2, n+1):
print("for문 ", i)
if i in num:
print("if문 ", i)
num -= set(range(2*i, n+1, i))
print("배수 뺀 후 ", num)
return len(num)
print(solution(10))
