11. 소수 찾기

 

2 부터 n 까지 각 숫자가 소수인지 판단해야된다.

 

---

간단하게 생각해보면

 

1. 소수인지 아닌지 판단하는 함수를 만든다.

2. n 보다 작은 수에 대해서 1의 함수를 각각 적용하여 갯수를 샌다

 

로 다음과 같다.

 

# 소수인지 확인하는 함수
def prime_num(n):
    for i in range(2,n):
        if n%i == 0:
            return 0
    return n

def solution(n):
    answer = 0

    for i in range(n+1):
        if prime_num(i) > 1:
            answer +=1
    
    return answer

 

그러면 예상하는 바와 같이 시간초과에 걸리게 된다. 

현재 for 문을 2번 사용해서 시간 복잡도가 O(n^2) 정도 된다.

 

 

이와 관련된 해결방법으로 

 

'3. 기사단원의 무기' 라는 글에서 시간 복잡도를 줄이는 로직을 적용한적이 있다.

https://js0616.tistory.com/97

3. 기사단원의 무기

 

 

소수를 구하는것도 결국 

 

N = A * B 의 꼴이며 소수를 구하는 부분에 대해서 1 ~ n 까지 모두 계산할 필요없이

1 ~ (n**(1/2)) 까지만 계산해봐도 소수인지 아닌지 알 수 있다. 

 

예를 들면 49 의 경우 

1 ~ 49 까지 모두 넣어서 약수의 갯수를 확인 하지 않고

1 ~ 7 까지만 계산해봐도 알 수 있음. 

 

따라서 1과 n 을 제외한 숫자 2부터 n**(1/2) 까지의 숫자 중에서 n 을 나누었을때

나머지가 0 인게 하나라도 나오면 소수가 아니라고 판단  할 수있다.

 

---

# 소수인지 확인하는 함수
def prime_num(n):
    for i in range(2,int(n**(1/2))+1):
        if n%i == 0:
            return 0
    return n

# main 함수
def solution(n):
    answer = 0

    for i in range(n+1):
        if prime_num(i) > 1:
            answer +=1
    
    return answer

 

 

 

다음과 같이 효율성 테스트를 통과하는걸 확인 할 수 있다.