에라토스테네스의 체3 [BaekJoon 4948번] 베르트랑 공준(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net [문제 설명] 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 .. PS/BaekJoon 2022. 12. 5. [BaekJoon 2960번] 에라토스테네스의 체(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net [문제 설명] 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌.. PS/BaekJoon 2022. 8. 2. [Algorithm] 에라토스테네스의 체 위 짤은 인터넷을 돌아다니다가 재밌어서 가져와봤습니다. 무튼 글을 시작하자면 알고리즘 문제를 풀다보면 소수 판별하라는 문제가 종종 보입니다. 해당 문제를 해결하기 위해선 소수 판별하는 알고리즘을 사용해야 합니다. 그래서 알고리즘 중에 '에라토스테네스의 체'가 가장 시간 복잡도도 우수하기 때문에 머릿속에 저장할 겸 정리해보려고 합니다. 목차 소수란 에라토스테네스의 체에 대해서 에라토스테네스의 체 구현(C++) 소수란 소수는 1과 자기 자신만을 약수를 갖는 1보다 큰 자연수입니다. (참고로 1은 소수가 아닙니다.) 에라토스테네스의 체에 대해서 에라토스테네스의 체는 이름 그대로 무언가를 찾기 위해 체를 걸러내듯, 소수를 찾는 방법입니다. 알고리즘은 2부터 찾고자하는 수까지 나열하고 1을 지웁니다. 1 다음으로.. Algorithm 2022. 8. 2. 이전 1 다음