백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)
보기에 간단해 보이는 문제이다. sosu()메소드를 만들어서 m부터 n까지의 소수를 차례대로 구하는 코드를 작성했으나 시간 초과로 실패 이러한 시간 초과 문제를 해결하기 위해서는 에라토스테네스의 체를 이용하면 된다. '에라토스테네스의 체' 란 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나간다. 차례대로 지워나갔을 때 남아있는 수는 소수가 된다. 즉 배열을 생성한 후 에라토스테네스의 체를 이용하여 2의배수, 3의배수,... 를 차례대로 걸러내고 남는것을 출력하면 되겠다. n+1개의 배열을 만들고 2의 배수부터 ..
