[프로그래머스] 소수찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

1. 소수를 찾아 저장할 리스트를 생성한다. li = list()
2. 소수의 시작인 1부터 시작하여 입력받은 수 사이에서 소수를 찾는다. for i in range(2, n + 1)
3. 수를 일단 리스트에 추가한다. li.append(i)
4. 소수인지 판별할 때는 2부터 자기 이전까지 수 중 모두 나누어 떨어지지 않으면 그 수는 소수이다. 하지만 이렇게 판별하게 되면 많은 시간이 소요된다.
5. 이때 판별하는 수의 제곱근을 구하여 해당 제곱근 이전의 정수까지 나누어 봤을 때 나누어 떨어지지 않는다면 해당 수는 소수라고 할 수 있다.
6. 하여 2부터 해당 수의 제곱근을 반올림한 결과까지 반복하며 for j in range(2, round(i ** 0.5) + 1)
7. 해당 수가 나누어 떨어지면 if (i % j == 0)
8. 소수가 아니므로 추가했던 수를 제거한다. li.pop()
9. 소수가 아닌 것으로 판별되었으므로 판별을 종료한다. break
10. 소수를 모두 찾았으면 해당 개수를 저장한다. answer = len(li)

반응형

3. 소스코드

def solution(n):
    answer = 0
    
    li = list()
    for i in range(2, n + 1):
        li.append(i)
        for j in range(2, round(i ** 0.5) + 1):
            if (i % j == 0):
                li.pop()
                break
    
    answer = len(li)
    return answer