Java) BOJ 1929. 소수 구하기
문제 링크
제한
- 시간 제한 : 2 초
- 메모리 제한 : 256 MB
문제
- M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
- 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
👀 풀이
- M이상 N이하의 수들을 소수를 판별하는 연산을 해서 소수면 출력했다.
- 하지만 정직하게 2부터 i까지의 수의 나머지를 구하면서 소수를 판별하면 시간이 오래 걸리기 때문에 i의 제곱근 만큼만 반복하는 알고리즘을 썼다.
- i의 제곱근만큼만 반복해도 소수인지 판별이 되는 이유는 제곱근을 넘어가는 수 부터는 앞전에 구했던 곱해서 i가 되는 수들이 순서만 바뀌어서 똑같이 나오기 때문이다.
- 예를 들어 i=16라면
- 1*16
- 2*8
- 4*4
- 8*2
- 16*1
- 위와 같이 16의 제곱근인 4를 기점으로 앞전에 나왔던 수들이 순서만 바뀌어서 나온다.
-
그래서 제곱근을 초과하는 수에 대해 소수를 판별하는 연산을 하는 것은 생략해도 결과에 영향이 없다.
- https://notepad96.tistory.com/entry/C-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0
- 예전에 참고했던 글인데 언어 상관없이 개념적으로 참고하기 좋은 글이다.
결과
- 시간 : 1128 ms
- 메모리 : 29424 KB