코딩 연습

프로젝트 오일러 문제를 풀다보면 두 자연수의 최대공약수를 구해야 하는 경우가 빈번히 발생한다. 이때 유클리드 알고리즘(유클리드 호제법)을 이용하여 쉽게 최대공약수를 구하는 함수를 소개하고자 한다. def gcd(a, b): if a < b: (a, b) = (b, a) while b != 0: (a, b) = (b, a % b) return a 먼저 \(a\) 쪽이 항상 크도록 해주고, \(a\)와 \(b\) 의 최대공약수는 \(b\)와 \(a\) 를 \(b\)로 나눈 나머지와의 최대공약수와 같기 때문에, 나머지가 \(0\) 이 될때까지 이 작업을 반복해 준다. \(b\) (=나머지)가 \(0\) 일 때의 \(a\) 값이 \(a, \;b\) 의 최대공약수가 된다.

처음으로 파이썬에서 완전제곱수를 판별하는 함수를 만들려고 단순히 제곱근이 정수이면 된다고 생각해었다. 그래서 다음과 같은 함수를 만들었었다. def issquare(n): temp = n ** 0.5 if int(temp) == temp: return True else: return False 그런데 이게 제대로 작동을 안하는 것이었다. \(89011483755109777\) 은 완전제곱수가 아닌데도 제곱근이 정수로 출력되는 것을 볼 수 있다. 소숫점 이하가 아주 작을 경우 버림을 해버리기 때문에 발생하는 일이다. 따라서 이것만으로는 완전제곱수인지 판단하기 어려우므로, 제곱근을 다시 제곱해서 원래의 수가 나오는지 확인해야 한다. def issquare(n): temp = n ** 0.5 if int(te..

import math def primecheck(n): if n == 2 or n == 3: return True if n % 2 == 0 or n == 1: return False for i in range(3, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True if __name__ == "__main__": yn = "y" while yn == "y" or yn == "Y": n=input("소수인지 확인하고 싶은 수는? ") if primecheck(int(n)): print("%d는(은) 소수입니다." % int(n)) else: print("%d는(은) 합성수입니다." % int(n)) yn = input("계속 확인하시겠습니..

프로그래밍을 이용하여 수학문제를 풀때 의외로 소인수 분해를 해야할 일이 많아진다. 소인수 분해의 원리는 다들 잘 알고 있으리라 생각된다. 일단 소수들의 리스트를 만들어 놓고, 그것들을 하나씩 불러내서 소인수 분해 하고자 하는 수를 나누어 떨어지는 동안 계속 나눈다. 나누어 떨어지지 않게 되면 소수들의 리스트에서 다음 소수를 불러내 똑같은 작업을 반복한다. 이 작업을 몫이 1이 될때까지 계속한다. 예를 들어, 80을 소인수분해 하면 (몫, 소인수)가 다음과 같이 변해 갈 것이다. (40, 2) (20, 2) (10, 2) (5, 2) 이제 5는 2로 나누어 떨어지지 않으므로 3을 불러낸다. 그러나 5는 3으로도 나누어 떨어지지 않으므로 5를 불러낸다. (1, 5) 이제 몫이 1이 되었으므로 소인수 분해를 ..

순열의 경우를 나열하는 것과 조합의 경우를 나열하는 것은 비슷한 듯 비슷하지 않은것 같다. 일단 원리는 다음과 같다. abcde 중 3개를 선택하는 조합을 생각한다면 먼저 abc 가 될 수 있고, 이제 마지막 알파벳을 하나씩 오른쪽으로 옮겨가며 선택한다. 그래서 얻을 수 있는 것이 abd, abe가 된다. 알파벳이 마지막까지 오게 되면 이제 알파벳 b을 오른쪽으로 옮겨 똑 같은 작업을 반복한다. 그래서 얻을 수 있는 것이 acd, ace가 된다. 다시 c를 오른쪽으로 한 칸 옮기면 ade가 선택된다. 이제 a를 오른쪽으로 한 칸 옮겨 같은 작업을 반복한다. 그래서 얻을 수 있는 것이 bcd, bce가 되고, 다시 c를 오른쪽으로 한 칸 옮겨 얻는 것이 bde가 된다. 마지막으로 b를 한 칸 오른쪽으로 옮..

다음은 소수를 찾기 위해 내가 겪은 시행 착오 과정이다. 자연수 \(n\) 이 소수(prime number) 인지 체크하는 가장 단순한 방법은 \(n\) 이 \(1

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible. In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum \(-42\). We wish to make such a triangular array with one thousand rows, so we generate \(500500\) pseudo-random numbers \(s_k\)..

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is \(16\; (=8+7+1)\). −25329−6513273−18−4 8 Now, let us repeat the search, but on a much larger scale: First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator": For ..

We can easily verify that none of the entries in the first seven rows of Pascal's triangle are divisible by \(7\): 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 However, if we check the first one hundred rows, we will find that only \(2361\) of the \(5050\) entries are not divisible by \(7\). Find the number of entries which are not divisible by \(7\) in the first one billion \(\l..

In a\(3 \times 2\) cross-hatched grid, a total of \(37\) different rectangles could be situated withing that grid as indicated in the sketch. There are \(5\) grids smaller than \(3 \times 2\), vertical and horizontal dimensions being important, i.e. \(1 \times 1\), \(2 \times 1\), \(3 \times 1\), \(1 \times 2\) and \(2 \times 2\). If each of them is cross-hatched, the following number of differe..