코딩뚠뚠

풀이일시 : 2020-12-24 ​ 문제 : 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오...

풀이일시 : 2020-09-21 ​ 문제 : 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, ..

풀이일시 : 2020-09-14 ​ 문제 : 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. ​ 입력 : 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수..

풀이일시 : 2020-09-11 ​ 문제 : M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. ​ 입력 : 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. ex) 3 16 ​ 출력 : 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. ex) 3 5 7 11 13 ​ 풀이 : N과 M 사이에 있는 소수들을 구해야 하는데 다만 숫자의 크기가 최대 1000000까지 나올 수 있다는 점에서 반드시 에라토스테네스의 체를 이용하여 소수를 판별해야한다. dbstndi6316.tistory.com/53 [기본문제풀이] 에라토스테네스의 체 풀이 일시 : 2020-08-13 ​ 에라토스테네스의 체..

풀이 일시 : 2020-08-13 ​ 에라토스테네스의 체 : 소수(prime number) 판별 알고리즘이다. 어떤 수로도 나뉘어지지 않아야 되기 때문에 그 수를 나눠보면서 판단할 수 있다.. -> 이 방법은 O(N)의 복잡도를 갖는다. 모든 수를 체크했기 때문이다. 제곱근까지만 약수의 여부를 검증한다 -> 이 방법은 O(N^(1/2))로 계산이 가능하다. -> int end = (int)sqrt(x)로 두고 x의 소수를 구하려면 2~end까지 체크한다. ​ 문제 : 에라토스테네스의 체를 이용하여 소수를 출력하여라. ​ 풀이 : 1. 이차원 배열을 생성하여 값을 초기화한다. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자신은 지우지않는다.) 3. 3의 배수도 지운다. (자신..