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

안녕하세요 뚜디 입니다

코딩테스트 연습 - 소수 찾기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 소수 찾기

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

1. 연습 문제

• 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

• 제한 조건

n은 2이상 1000000이하의 자연수입니다.

• 입출력 예

n	result
10	4
5	3

2. 문제 풀이

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

문제 풀이 전 일반적으로 문제를 풀게될 경우 효율성 테스트에서 통과를 하지 못하게 됩니다.
따라서, 저희는 소거법을 통해 문제를 풀어 효율성 테스트에서 통과를 하도록 합니다.

1. 임의의 리스트를 선언하여 인자값을 0으로 초기화
2. 반복문을 소수인 2부터 시작하여 소수가 아닌 수를 찾도록 한다.
3. 소수의 배수는 소수가 아니므로 임의의 list를 1로 변경한다.

3. 소스 코드

def solution(n):
    answer = 0
    list = [0 for i in range(n+1)]

    for i in range(2, n+1):
    	# list 인자값이 1일 경우 소수가 아님
        if (list[i]):
            continue
        # 위 조건문을 통과했다면 소수이므로 +1
        answer += 1
        # 소수인 숫자의 배수는 소수가 아니므로 list의 인자값을 1로 변경
        for j in range(i+i, n+1, i):
            list[j] = 1

    return answer

4. 결과