에라토네스의 채
-
BOJ) 베르트랑 공준알고리즘/백준 2020. 6. 24. 17:11
베르트랑 공준 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 �� www.acmicpc.net 풀이 에라토네스의 채를 확실히 익혔는지 확인하려고 풀었다. 방법은 바로 이전 포스팅과 같기 때문에 딱히 포스팅할 말은 없다. 에라토네스 채는 자신의 배수에 대해서 소수가 아님을 체크해주는 방식이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class FindPrimeNums_4948 { final..
-
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문을 다시 도는 부분이 불필요하다고 느..