https://school.programmers.co.kr/learn/courses/30/lessons/12921
프로그래머스 Lv1
문제 제목 : 시저 암호
문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 사항
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
풀이
첫 풀이를 이렇게 하니
해결을 위해서 에라토스테네스의 채를 이용해야 한다.
에라토스테네스의 채
- 2 부터 소수를 구하고자 하는 수까지 수를 나열한다.
- 2부터 2의 배수를 지우고, 2는 소수이므로 소수의 배열에 넣는다.
- 3부터 3의 배수를 지우고, 3은 소수이므로 소수의 배열에 넣는다.
- ...
- 이 과정을 반복한 후 소수 배열의 길이를 구하면 몇개의 소수가 있는지 찾을 수 있다.
