- Total
목록오뚝이 개발자/알고리즘 (27)
꿈꾸는리버리
[백준 알고리즘 4948] 베르트랑 공준
https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (백준 1929 소수구하기 문제와 동일) 에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 해당 수의 제곱근까지만 나누어보는 것: 쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3..
[백준 알고리즘 11653] 소인수분해
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 방법 : 재귀함수를 이용해서 문제를 풀었다. 작성한 코드는 다음과 같다. #include using namespace std; void calculate(int n){ if( n
[백준 알고리즘] 1929 소수구하기 C++
문제 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다. 해당 수의 제곱근까지만 나누어보는 것: 쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3,4,5,6,7,8,...,18 -> 루트 18은 대략 4. xx이다...