에라토스테네스의 체1 에라토스테네스의 체 해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~ 0. 소수 소수란 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다. 1. 에라토스테네스의 체 란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 그 중 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우에 가장 좋은 효율을 보인다. (이때 시간 복잡도는 O(Nlog (logN))이다. 하지만 필요없는 숫자들의 소수도 판별해야 하기에 숫자가 커지면 커질수록 비효율적이다. 또한, 에라토스테네스의 체 과정상 주어진 정수범위 N의 크기만큼 리스트나 배열등을 할당해야하기 때문에 메모리가 많이 필요하다는 것도 단점이다.) 고대 그리스의 수학자 에라토스테네스가 .. 2024. 1. 16. 이전 1 다음
