인공지능 개발일지

안녕하세요 여러분:) 이번시간에는 에라토스테네스의 체 알고리즘에 대해 알아봅시다. 에라토스테네스의 체는 유클리드 호제법과 더불어 알고리즘을 공부하셨다면, 한 번쯤은 들어봤을 알고리즘이죠? ㅎㅎ. 1. 에라토스테네스의 체란? 에라토스테네스의 체란 간단하게 말해서 시작범위와 끝 범위의 수가 주어졌을 때 그 수 가운데 있는 수 중에서 소수 리스트를 구할 수 있는 알고리즘입니다! 기본적으로 1부터 100까지 수 중에서 소수를 구하여라.라는 문제가 주어졌을 때 우리는 한 수에 대해서 모두 이중 반복문을 돌려서 1과 자기 자신을 포함한 약수가 어떤 수가 있는지 구하는 방법이 있죠? 그런데 이 방법을 사용하면 모든 수에 대해서 이중 반복문을 돌려야 하므로 시간 복잡도가 O(n²)으로 매우 큽니다. 이때 에라토스테네스..