Computer/알고리즘&백준

[백준] [C++] 4948 베르트랑 공준

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 이 문제는 1929번 문제와 크게 다르지 않다. 범위만 n~2n으로 바뀌었을 뿐 1929번 풀 때는 삽질을 엄청나게 했는데, 1929 풀고 나니 이 문제는 쉽게 풀렸다 https://katteniiki.tistory.com/23 [백준] [C++] 1929 소수 구하기, 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에..

[백준] [C++] 1929 소수 구하기, 에라토스테네스의 체

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 처음에는 그냥 무작정 짝수 거르고 루프 돌렸더니 시간초과 뜸 그래서 찾아봤더니 '에라토스테네스의 체'라는 것이 있다카더라 에라토스테네스의 체는 특정 범위가 주어졌을 때 그 범위 내의 소수들을 판별할 수 있는 방법이다. 마치 체로 거르듯 소수들의 배수를 지워나가다보면 남는 것은 소수임을 이용한다. 2부터 수들을 나열한 다음, 2는 소수이므로 남겨두고 2의 배수들을 지운다. 3 역시 소수이므로 남겨두고 3의 배수를 지운다. 이런 방..

[백준] [C++] 11653 소인수분해

1일 1백준 시작 C++ 배우느라 미뤄뒀던 백준 다시 시작하기로 함 현재 티어 실버5 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net #include int main() { int num; std::cin >> num; if (num == 1) return 0; for (int i = 2; i