알고리즘

[백준] 에라토스테네스의 체

[백준] 2960번 에라토스테네스의 체 자바 들어가며 오늘은 시간 복잡도를 고려하여 소수를 찾는 알고리즘은 에라토스테네스의 체와 관련 문항에 대해서 정리해보려 한다. 에라토스테네스의 체 에라토스테네스의 체는 소수를 찾는 대표적인 알고리즘이다. 위 이미지는 에라토스테네스의 체의 원리를 잘 나타내고 있다. 원리 2부터 소수를 구하고자 하는 구간(N, 위 이미지에서는 120)의 모든 수를 나열한다.(주로 N+1까지의 int 배열을 생성한다.) 생성한 int 배열을 for문을 활용, i = 2부터 i