반응형
1929
-
BOJ) 소수 구하기알고리즘/백준 2020. 6. 24. 17:08
소수 구하기 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 소수를 구하는 문제를 풀어본지 오래돼서 에라토네스의 채 자체를 망각하고 있었다. 그래서 GCD를 통해 풀어야하나 생각하다가, 소수를 구하는 알고리즘이 있나 찾아봤다. 에라토네스의 채를 보고 존재가 다시 떠올랐다. 구현하는 방법은 까먹어서 방법을 익히기로했다. 1은 소수에 포함되지 않기 떄문에 2부터 시작하고, j에 해당하는 부분은 자신의 배수에 대해 표시를 해주는 것이다. 이후에, for문을 돌면서 소수를 찾아 출력해줬다. 하지만, for문을 다시 도는 부분이 불필요하다고 느..