[프로그래머스] 소수 찾기 (파이썬)

🗓️ 문제 설명

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하세요.
• 제한 사항
  • 2 ≤ n ≤ 1000000
• 입출력 예시

n	result
10	4
5	3

 

💻 코드

최종 코드

• 수정 사항
  >> 큰 자연수에 대해 런타임 에러가 발생하기 때문에 소수 판별을 위해 제곱근을 사용

 

코드 풀이

 

다른 사람 풀이

풀이 1번('에라토스테네스의 체'를 이용한 풀이방법)

• 에라토스테네스의 체
  • 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법
    1. 배열을 생성하여 초기화
    2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지움
       (지울 때, 자기자신은 지우지 않고, 이미 지워진 수는 건너뜀)
    3. 2부터 시작하여 남아있는 수를 모두 출력

1. 2번줄 : 2부터 주어진 수까지 들어있는 배열을 set로 생성
2. 4~6번줄 : 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지움
3. 7번줄 : 남아있는 소수의 갯수를 출력

 

⚙️ 시행착오

1차 시도

• 큰 자연수에 대해 시간초과