에라토스테네스의 체

1929. 에라토스테네스의 체https://www.acmicpc.net/problem/1929[풀이]일반적으로 n이 소수인지를 판별할 때 n을 2부터 n-1까지 나눈 나머지로 판별한다. 시간복잡도가 O(n)이다.그러나 m과 n 사이의 소수를 판별할 때는 이중 반복문이 사용되어 O(n^2)이 된다. n의 최대크기가 1,000,000정도로 커졌을 때 위와 같은 방식으로는 시간초과를 피할 수 없다. 그래서 에라토스테네스의 체라는 수학적 방법을 사용하게 되는데, 그냥 이게 더 빠르구나하고 외우고 활용하는게 좋을 것 같다. 우선 최대크기의 배열을 하나 잡는다. 나는 a[1000001]라고 잡았다.1) 그리고 각 인덱스값을 값으로 할당해준다.2) 2부터 n까지 돌며 해당 배열의 값 중에 '어떤 수의 배수'인 값만 ..