백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)

백준알고리즘 #1929 소수 구하기 문제

보기에 간단해 보이는 문제이다.

오류 코드(시간 초과)

sosu()메소드를 만들어서 m부터 n까지의 소수를 차례대로 구하는 코드를 작성했으나 시간 초과로 실패

 

 

 

이러한 시간 초과 문제를 해결하기 위해서는 에라토스테네스의 체를 이용하면 된다.

 

네이버 지식백과 https://terms.naver.com/entry.nhn?docId=1179083&cid=40942&categoryId=32204

'에라토스테네스의 체' 란 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나간다. 차례대로 지워나갔을 때 남아있는 수는 소수가 된다.

 

 

즉 배열을 생성한 후 에라토스테네스의 체를 이용하여 2의배수, 3의배수,... 를 차례대로 걸러내고 남는것을 출력하면 되겠다.

소수구하기 코드(에라토스테네스의 체)

n+1개의 배열을 만들고 2의 배수부터 차례대로 a[2], a[4] ... 의 수를 하나씩 증가시킨다.

이 for문이 끝나고 났을 때 a[n]의 값이 0(초기값)인 것들을 출력하면 되는데, 이 때 1을 생각하지않으면 틀렸다고 나온다..ㅠㅠ

그래서 마지막 for문에 if(m==1) a[1]++; 구문을 넣어주면 완성.

결과

저 1을 생각못하고 엄한것들을 건드려서 엄청나게 많은 오답들을 제출했지만... 

결국 1을 따로 빼서 처리해주면서 정답인정!