[Python] 연습문제 : 소수찾기

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

 

 

💡문제💡

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 return 하시오.

 

 

[제한 사항]

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

 

 

코드 및 풀이👩🏻‍💻

---

수학에서 에라토스테네스의 체를 이용해 소수를 찾을 수 있다.

 

 

❌에라토스테네스의 체 알고리즘❌

 

 

 

1. 2부터 소수를 구하고자하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓴 후 자기 자신을 제외한 2의 배수를 모두 지운다.

3. 남아있는 수 가운데 가장 작은 수 3은 소수이므로 오른쪽에 3을 쓴다.

4. 자기 자신을 제외한 3의 배수를 모두 지운다.

5. 남아있는 수 가운데 가장 작은 수 5는 소수이므로 오른쪽에 5를 쓴다.

....

6. 위 과정을 반복하면 구하는 구간의 모든 소수를 구할 수 있다.