본문 바로가기

Programming/Project Euler118

[C/C++] 프로젝트 오일러 #27 : 2차식 소수 생성 Project Euler #27 “Quadratic Primes” 문제는 다음을 요구합니다:주어진 이차식  \(n^2 + an + b\) 에서  n 은 0부터 시작하는 정수이고,  a 와  b 는 정수 범위  |a| 요약:1.  \(n^2 + an + b\) 가 연속된  n 에 대해 최대한 많은 소수를 생성하도록 하는  a 와  b 를 찾는다.2. 그런  a 와  b 의 곱을 구한다. \( n^2 + n + 41 \) 식은 너무나도 유명한 2차식 소수 생성 공식입니다.  n의 값이 0부터 39까지 총 40개의 연속된 소수를 생성합니다.더 많은 소수를 내기 위해서는 더 큰 숫자가 필요하겠죠.  일단 문제에 있는 것을 조금 더 보자면,\[ n^2 + an + b \quad \text{where} \quad .. 2015. 2. 28.
[C/C++] 프로젝트 오일러 #26 : 순환고리 이번 문제는 가장 긴 순환고리를 찾는 문제입니다.  사실 순환고리는 오일러의 수 문제로 귀결됩니다.  오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다.\[ n = \prod_{p_k \mid n} p_k^{a_k} \]라고 한다면,  오일러의 수는\[ \phi(n) = \prod_{p_k \mid n} (p - 1)p^{a_k - 1} \]이라고 할 수 있습니다.즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다.  n이 소수라면 n-1 이 오일러의 수가 됩니다.가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다.  10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 .. 2015. 2. 27.
[C/C++] 프로젝트 오일러 #25 : 1000자리 피보나치 수열항 구하기 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다.  피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요.  꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다.  기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. \[ F_{n+2} = F_n + F_{n+1} \] 점화식을 보면 아주 간단한 형태입니다.  전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서  첫번째 항과 두번째 항이 초기값으로 주어져야 합니다.  첫번째 항은 1, 두번째 항은 1입니다.  자연수 범위.. 2015. 2. 17.
[C/C++] 프로젝트 오일러 #24 : 백만번째 순열 수 구하기 프로젝트 오일러 #24 백만번째 순열 수 구하기 문제는 0부터 9까지의 숫자로 이루어진 모든 순열(permutation)을 사전 순서(lexicographic order)로 정렬했을 때, 백만 번째 순열을 구하라는 것입니다. 우리가 진법을 계산할 때, 과연 어떻게 할까요?예를 들어서 723 을 8진법으로 계산한다면요?이 계산을 위해서 우리는 나누기 연산을 계속 하게 됩니다.  중학교 수학을 들추어 보면 보통 다음과 같이 계산을 합니다.으로 723은 8진수로 \(1323_8\)으로 표시가 됩니다. 이것을 수식으로 표현하면 다음과 같이 표현할 수 있습니다.\[ 723 = 1 \cdot 8^3 + 3 \cdot 8^2 + 2 \cdot 8^1 + 3 \cdot 8^0 \]이야기는 우리는 8의 3승부터 차례로 .. 2015. 1. 27.
[C/C++] 프로젝트 오일러 #23 : 초과수의 합으로 표현 안되는 자연수들의 합 Project Euler #23 - Non-Abundant Sums 문제는 다음을 요구합니다.자연수는 “부족수(Deficient number)”, “완전수(Perfect number)”, 또는 “과잉수(Abundant number)” 중 하나로 분류됩니다. 특정 숫자의 진약수들의 합이 해당 숫자보다 작은 경우, 그 숫자는 부족수입니다. 합이 정확히 같은 경우에는 완전수라고 하고, 더 큰 경우에는 과잉수라고 합니다. 예를 들어, 숫자 12의 진약수는 1, 2, 3, 4, 6이고, 이들의 합은 16이므로 12는 과잉수입니다.문제는 다음 두 가지를 해결하라고 요청합니다:1. 두 개의 과잉수의 합으로 나타낼 수 없는 모든 양의 정수를 “비과잉합(non-abundant sums)“이라고 정의합니다. 이러한 모든 .. 2015. 1. 26.
[C/C++] 프로젝트 오일러 #22 : 이름 점수 구하기 이 문제에서는 주어진 텍스트 파일에 포함된 이름들의 점수 합계를 계산하는 것을 요구합니다. 문제를 해결하기 위한 단계는 다음과 같습니다:1. 입력 파일 읽기: 파일에서 각각의 이름이 큰따옴표로 묶여 있는 쉼표로 구분된 단일 행 데이터를 읽습니다.2. 이름을 알파벳 순으로 정렬: 이름 리스트를 알파벳 오름차순으로 정렬합니다.3. 이름 점수 계산:• 각 이름의 점수를 계산합니다. 이름의 점수는 이름을 구성하는 각 글자의 알파벳 값을 더하여 구합니다 (A=1, B=2, …, Z=26).• 해당 이름 점수에 정렬된 순서(1부터 시작하는 인덱스)를 곱합니다.4. 전체 점수 계산: 모든 이름 점수를 합산하여 최종 결과를 구합니다.예를 들어, 파일에 "COLIN", "ALEX", "BOB"가 포함되어 있다면, 정렬된.. 2015. 1. 25.
728x90

티스토리툴바