[JAVA/자바] 백준 1929번: 소수 구하기

문제 풀이 1 (제곱근을 사용한 일반 풀이) 1. 1이면 continue해주고 2. 2부터 현재 수의 제곱근까지 반복문을 돌려 나누어 떨어지면 cnt++를 해준다. 3. 이때 나누어 떨어지는 수가 하나라도 있다면 반복문을 탈출한다 (소수가 아니다) 4.

반복문을 다 돌고 cnt가 0이면 출력해준다. (소수 출력) 풀이 2 (에라토스테네스의 체) 에라토스테네스의 체를 이용한 풀이!

프로그래머스에서도 이 알고리즘을 사용하여 풀이를 한 적이 있다. 에라토스테네스의 체는 2의 제곱, 3의 제곱, 4의 제곱....을 소거하여 남는 수가 소수라는 원리이다!

1. 마지막수 + 1만큼의 배열을 선언하고 2.

배열의 0번째와 1번째는 true로 바꿔준다. (0과 1은 소수가 아니다..........