[알고리즘] 프로그래머스 | 소수 찾기 Lv.1

소수 찾기

#수학 #에라토스테네스의 체

 

답: 

이중 for 문을 피하기 위해 검증함수를 따로 빼내었다. 

def is_prime(n):
    new_n = int(n**0.5) + 1
    for i in range(2, new_n):
        if n % i == 0:
            return False
    return True

def solution(n):
    answer = 0
    for i in range(2, n + 1):    
        if is_prime(i) == True:
            answer += 1
    return answer

 

 

다른 사람의 풀이

 1)

def solution(n):
    answer = 0
    for i in range(2, n+1):
        if i == 2:
            answer += 1
            continue
        for j in range(2, int(i ** (1/2)) + 1):
            if i % j == 0:
                answer -= 1
                break
        answer += 1
    return answer

 

2)

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)

+++

• for i in range(2,n+1): --> for i in range(2,int(n**0.5)+1): 로 바꾸면 계산 횟수가 줄어서 빨라질 것 같습니다.
•  

  num-=set(range(2*i,n+1,i)) --> num -= set(range(i*i,n+1,i)) 같은 관점에서 이렇게도 수정해도 될 것 같습니다.

 

문제 분석 및 해석

자연수 n이 주어지면 1 ~ 해당 수까지의 소수 구하기

 

 

>> 풀이생각

처음 생각

1) 1 ~ n 사이의 list만들기
2) for range()문 : 1 ~ n // 2 까지의 수로 나누어지지 않는 수는 소수?
3) 소수인 것은 list에 append해주기
4) list count하여 return 하기

 

 

! 다시 생각

이전 에라토스테네스의 체를 공부했던 것을 떠올려보자.

몫이 아니라 제곱근까지 range()로 검증하면 되는 것이었다!

!! math.sqrt(n) + 1 혹은 new_n = int(n**0.5) + 1 으로 제곱근을 구한다

 

range()에 2부터의 숫자를 넣고 검증한 후 True면 answer에 더한다.

 

 

 

 

과정1.

 

2부터 자연수 n까지의 list를 만들고 answer에 얕은 복사를 한다.

 

def solution(n):
    numbers = [i for i in range(2, n+1)]
    answer = numbers[:]

 

 

제곱근을 new_n으로 정의하고 

numbers list에 들어있는 숫자들을 2 ~ 제곱근 까지 검사한 후 얕은 복사해둔 answer에서 지워준다

이후 answer의 길이를 return

  

    new_n = int(n**0.5)
    for number in numbers:
        for i in range(2, new_n + 1):
            if number % i == 0:
                answer.remove(number)

    return len(answer)

 

테스트케이스1 자연수 10은 잘 구해졌는데,

테스트케이스2, 자연수 5에서 계속 실패했다.

[2, 3, 4, 5] 로 4를 걸러내지 못하는 오류가 계속 생김

 

그리고 전체 테스트를 실행하였을때 런타임 / 시간초과 오류로 테스트를 모두 통과하지 못했다.

 

 

 

과정2.

 

이중 for문과 list 조작으로 급격하게 오른 시간복잡도가 문제였던듯

for문 중첩시 시간복잡도는  O(n^2) 이다.

 

 

그래서 is_prime인지 검사해주는 검증함수를 분리해 작성

 

def is_prime(n):
    new_n = int(n**0.5) + 1
    for i in range(2, new_n):
        if n % i == 0:
            return False
    return True

 

 

True값인 경우 answer에 +1을 더해 결과를 return한다.

 

def solution(n):
    	...   
        if is_prime(i) == True:
            answer += 1
    return answer

 

---

느낀점:

이전에 공부했던 것이 새록새록 생각나는 문제였다.

약간의 검색찬스로 다시 공부하고 풀어보았는데, 어려웠지만 재밌었당