[프로그래머스] 소수 찾기: python3

def isPrime(num):
    for i in range(2, int(num**(0.5))+1):
        if num%i == 0:
            return False

    return True

def solution(n):
    answer = 0

    for i in range(2, n+1):
        if i>5:
            if i%2 == 0 or i%3 == 0 or i%5 == 0:
                continue

        if (isPrime(i)):
            answer += 1

    return answer

<내 풀이 분석>

# isPrime함수

num을 2~sqrt(num)로 나눔 => 나누어떨어지면 1과 자기자신 외에 약수가 있다는 뜻(소수가 아님) => False반환

                                    => 어떤 수로도 나누어 떨어지지 않으면 1과 자기자신만 약수(소수) => True반환

# solution

2부터 n까지의 수 중 2의 약수, 3의 약수, 5의 약수를 제외한 수들에 대해 isPrime함수를 적용

=> isPrime이 True라면 소수라는 뜻, answer += 1

 

 

- 2~sqrt(num)까지만 나눠보면 그 수가 소수인지 판별할 수 있음

- 2의 약수, 3의 약수, 5의 약수를 제외하면 거의 대부분의 수가 걸러지기 때문에 시간이 많이 줄어듦(이걸 안해주니까 시간 초과가 됨)

    // 근데 출제자 의도는 이게 아닐 것 같다.

 

 

 

 

 

+) 에라토스테네스의 체 이용한 다른 풀이

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)

좋아요를 제일 많이 받은 풀이인데 그럴 만하다. 

1. set에 모든 수를 넣는다.

2. set에서 2의 배수들을 빼고, 3의 배수들을 빼고, (4는 4의 배수에서 제외) 5의 배수들을 빼는 식으로 소수가 아닌 수들을 걸러낸다.

3. 마지막으로 set에 남은 수들은 소수