소수 판별 알고리즘1

• 

  [Algorithm] 에라토스테네스의 체 위 짤은 인터넷을 돌아다니다가 재밌어서 가져와봤습니다. 무튼 글을 시작하자면 알고리즘 문제를 풀다보면 소수 판별하라는 문제가 종종 보입니다. 해당 문제를 해결하기 위해선 소수 판별하는 알고리즘을 사용해야 합니다. 그래서 알고리즘 중에 '에라토스테네스의 체'가 가장 시간 복잡도도 우수하기 때문에 머릿속에 저장할 겸 정리해보려고 합니다. 목차 소수란 에라토스테네스의 체에 대해서 에라토스테네스의 체 구현(C++) 소수란 소수는 1과 자기 자신만을 약수를 갖는 1보다 큰 자연수입니다. (참고로 1은 소수가 아닙니다.) 에라토스테네스의 체에 대해서 에라토스테네스의 체는 이름 그대로 무언가를 찾기 위해 체를 걸러내듯, 소수를 찾는 방법입니다. 알고리즘은 2부터 찾고자하는 수까지 나열하고 1을 지웁니다. 1 다음으로.. Algorithm 2022. 8. 2.