[programmers] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

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

발상

주어진 수까지 소수를 판별하여 총 개수를 세는 문제이다.

소수판별 알고리즘을 효율적으로 작성하는 것이 핵심이다.

의사코드

1. 고정 탈출조건(n=2, n=3) 정의
2. 반복문(n=2, 제곱근까지)
  1. 나누어 떨어지면 0
  2. 아니면 소수
3. 총 합 반환

 

개선

소수 판별 알고리즘은 소인수분해와 같이 수의 특징을 다루는 문제여서 자주 보았던 문제이다.

핵심은 자신과 1을 제외하고 나누어지지 않아야 되므로, 탐색범위를 제곱근 이하까지 줄일 수 있다.

또한 2 이상의 짝수들도 제외할 수 있기 때문에 몇가지 조건을 주면 더 빠른 알고리즘을 작성할 수 있을 것이다.