하루에 하나-14(미완성)

정인창·2021년 9월 21일
0

코딩테스트 연습

목록 보기
14/19

def solution(n):
    answer = 0
    for i in range(2, n+1):
        for j in range(1, i+1):
            ## 소수가 아닌경우
            if (i % j == 0) & (j not in [1, i]):
                answer += 1
                break

    return n - 1 - answer
  • 소수가 아닌 숫자를 찾아서 전체에서 빼주는 게 나을거라 생각했습니다.
  • 시간 복잡도가 for문 O(n2)O(n^2)에 근사, 이중비교까지... 효율성은 개나 줘버렸습니다.
  • 구현도 제대로 하지 못했는데 이유가 뭘까요....
  • 우선 재귀함수를 써서 수정해보겠습니다!
profile
Data science

0개의 댓글