1. 문제 3908번: 서로 다른 소수의 합 (acmicpc.net) 3908번: 서로 다른 소수의 합 양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 여기서 덧셈의 순 www.acmicpc.net 2. 풀이 소수만을 사용하는데, 서로 다른 소수를 사용해야하고 k개를 사용해서 합했을때 n을 만드는 방법의 수를 구하기 일단 도구로 소수를 구해야겠지 n이 최대 1120이니까 1120이하의 소수를 모두 에라토스테네스의 체로 구해놓고 def get_prime(n): result = [1]*(n+1) for i in range(2,int(((n+1)**(1/2)))+1): if res..
https://en.wikipedia.org/wiki/Prime_gap Prime gap - Wikipedia Number 1 to 27 # gn pn n 1 1 2 1 2 2 3 2 3 4 7 4 4 6 23 9 5 8 89 24 6 14 113 30 7 18 523 99 8 20 887 154 9 22 1,129 189 10 34 1,327 217 11 36 9,551 1,183 12 44 15,683 1,831 13 52 19,609 2,225 14 72 31,397 3,385 15 86 155,921 14,357 16 96 360,653 30,802 17 en.wikipedia.org 1. 문제 23005번: Consecutive Primes (acmicpc.net) 23005번: Consecut..
1. 연속된 자연수의 합 2개의 연속된 자연수를 합해보면.. 1+2 = 3 2+3 = 5 3+4 = 7 4+5 = 9 ... 소수가 나올 수 있는데 3개 이상의 연속된 자연수를 합해보면.. 1+2+3 = 6 2+3+4 = 9 3+4+5 = 12 4+5+6 = 15 ... 일단 소수가 보이질 않는다.. 이게 우연일까? 자연수 x에 대하여 n개의 연속된 자연수의 합은 다음과 같이 나타난다. $$S = x + (x+1) + (x+2) + ... + (x+n-1) = nx + \frac{(n-1)n}{2}$$ 여기서 n이 3이상의 자연수일때, S가 반드시 합성수임을 보이고자 한다. 1) 만약 n이 짝수라면 $n = 2k$ 여기서 k는 2이상의 자연수이다. $$S = 2kx + k(2k-1) = k(2x + 2k..
1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 풀이 정수 n을 1,2,3만 사용해서 만드는 방법의 수를 구하는 문제 1) 여기서 1,2,3은 중복해서 사용 가능하다 2) 동일하게 사용해도 순서가 다르면 다르다고 취급한다. 즉 1+1+2와 1+2+1은 다른 경우이다. dp[n]을 n을 만드는 방법의 수로 정의하고, 일단 n이 11보다 작기 때문에 dp의 크기를 11까지 잡아준다. n을 만들려면 어떻게 해야할까? 1,2,3만 사용할 수 있기 때문에 3가지 경우가 가능하다. 1) n-1에서 1을 더하면 n n-1을 만드는 방법의 수 dp..
1. 문제 14860번: GCD 곱 (acmicpc.net) 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 N*M 테이블에서 최대공약수를 구해본다. 예를 들어 N = 10, M = 10이라고 한다면.. 1은 곱해봤자 의미없으니까 2부터 테이블에 몇개나 나타나는지 한번 찾아보면 5*5 = 25개 있다는 것을 알 수 있는데 이는 행과 열에서 2의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..
1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
