반응형 소수3 [백준/C++] 골드바흐흑흙의 추측 (No. 32647) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] A, B사이의 소수들의 합으로 K라는 수를 만들 수 있는지 라는 문제를 보고 처음에 단순히 경우의 수를 계산하면 안되겠다는 생각이 들었다. B-A 하지만, 모든 경우를 직접 계산하지 않고 소수의 합을 Memoization으로 몇 번 나왔는지 계산하면 중복되는 경우가 생기므로 빠르게 계산할 수 있겠다는 생각이 들었다. 예를 들어 2, 3, 5, 7의 소수가 있을 때를 아래 그림을 통해 생각해보자. 이렇게 덧셈을 해가며 계산하면 중복되는 경우가 생긴다.5의 경우 소수 5만 사용하는 경우와 2, 3을 더해 5를 만드는 .. 2024. 11. 13. [Algorithm/기본지식] 소수 판별하기 HTML 삽입 미리보기할 수 없는 소스 정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다. $$a=\sqrt{N}$$ $$N=b_1\times b_2\times ...b_n\ \left(N의\ 소인수\ 분해\right)$$ 임의의 정수 N의 제곱근을 a라고 한다. 정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다. a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다. 이를 활용하면 1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우 2. N이 소수가 아닐 때, a보다 크.. 2024. 1. 2. [백준/Python] 11653번 - 소인수분해 HTML 삽입 미리보기할 수 없는 소스 정수 N이 주어졌을 때, 소인수 분해를 해야한다. (단, 1 입력 시 출력X) HTML 삽입 미리보기할 수 없는 소스 정수 N을 소인수분해 하기 위해서, 정수 N이 소수인지 아닌지 판별하는 방법을 활용했다. HTML 삽입 미리보기할 수 없는 소스 정수 N의 제곱근을 a라고 했을 때, 정수 N의 소인수 중 a보다 크거나 같은 소인수가 존재 하면, 나머지 소인수는 전부 a보다 작거나 같을 수 밖에 없다. 그러므로 for 문을 이용해 2부터 N의 제곱근 사이의 수로 정수 N이 나눠지는지 확인하고, 나눠지고 남은 수를 출력하면 소인수 분해가 끝난다. N의 소인수들이 전부 a보다 작거나 같을 경우 정수 N의 소인수를 전부 구할 수 있다. N의 소인수 중 a보다 큰 소인수.. 2024. 1. 2. 이전 1 다음 반응형
