목록소수 찾기 (1)

ian의 개발일기장

[level1] 소수 찾기

1. 나의 풀이 원래는 다른풀이를 썼는데.. 효율성테스트로 인해서, 에라토스테네스의 체를 이용해야한다는것을 알았다. 에라토스테네스의 체는 수학에서 소수를 찾는 방법중에 하나이다. 2. 다른사람 풀이 주석에 풀이가 잘 나와있다. 3. 결론 효율성에 대해서 잘 생각해보고, 코드를 짜야겠다. 4. 정리 에라토스테네스의 체 = 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)자기 자신을 제외한 2의 배수를 모두 지운다.남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)자기 자신을 제외한 3의 배수를 모두 지운다.남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)자기 자신을..
Algorithms/Programmers 2018. 9. 22. 20:10
이전 Prev 1 Next 다음