[Programmers] 합성수 찾기

Q. 약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

Source: https://school.programmers.co.kr/learn/courses/30/lessons/120846

 

처음 직관적으로 생각한 방법은 n에서 소수의 개수를 빼는 것이었다

-> 전체를 순회하기보다 제곱근+1의 값까지 체크하여 소수여부를 판별한뒤 (성능,속도면에서 전체를 체크하는 것보다 제곱근까지만 체크하는 것이 빠르기 때문) 

-> 전체개수에서 소수의 개수를 빼서 리턴하자 

import math 

def solution(n):
    isPrime = 0
    for i in range (1, int(math.sqrt(n)) +1):
        if n % i != 0:
            isPrime += 1
    return n-isPrime

당연히.. n에서 소수의 개수를 빼는 것이기 때문에 오답이었다. 

 

그래서 이렇게 작성했다. 제곱근은 math 라이브러리를 사용해도 된다. 근데 이 방법은 이중 for문 사용이라 더 좋은 방법이 있으면 좋겠다는 생각이다

def solution(n):
    answer = 0
    for i in range(4, n + 1): #1,2,3은 소수이기에 4부터 시작 
        for j in range(2, int(i ** 0.5) + 1): 
            if i % j == 0:
                output += 1
                break
    return answer