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

프로그래머스 level1

문제

문제 풀이

에라토스테네스의 체

시간 초과

문제 리뷰

✓ 에라토스테네스의 체 풀이

‘에라토스테네스의 체’

• 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법

  소수는 1과 자기 자신으로만 나누어 떨어지는 수이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 
   그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

위의 그림을 보면서 이야기 해보자면
결론은 120의 제곱근인 11보다 작은 수의 배수들만 지워도
소수를 찾는 것이 가능하다는 것이다.
즉, 120 이하의 수 중 2, 3, 5, 7의 배수를 지우고 남는 수가 소수이다.

이 방법을 이용하여 2부터 n까지의 반복문 안에서
n의 제곱근까지 반복문을 돌려 소수인지 아닌지를 판별해주었다.

• 제곱근을 구하는 함수

Math.sqrt(double d)

---

✓ 시간 초과 풀이

처음에는 반복문을 이용하여 풀었다.
2부터 n까지의 반복문 안에서
또 다시 2부터 n까지 반복문을 돌려 자기 자신과만 나누어 떨어지는 수를 찾았다.
i와 j가 나누어 떨어지는 횟수가 1이면 자기 자신과만 떨어졌기에 소수가 되는 것이다.

답을 잘 나왔으나
정확도 테스트 10, 11, 13과 효율성 테스트 4개 모두 시간 초과가 되었다.
에라스토테네스의 체를 사용해보라는 팁을 보고 위와 같이 문제를 풀게 되었다.

TMI

에라토스테네스의 체..

1일 3알고리즘 완료🤓