정수론 (8) 썸네일형 리스트형 find (a, b) such that am + bn = gcd(m, n) #!/usr/bin/python ######################################### # Programming Challenges ISBN 8979142889 # ---------------------------------------- # problem 51 : Euclid Problem #---------------------------------------- # uva 10104 ######################################### # For given m, n, find a, b such that # am + bn = g ######################################### # Date : 2007.03.31 # Author : DwY.. 카마이클 수 ############################################ # ISBN89-7914-288-9 Programming Challenges # problem 50 : uva 10006 # Carmichael Numbers ############################################ TRUE = 1 FALSE = 0 def pow_mod(a, b, m): '''get the value of a**b mod m''' ret = 1 for i in range(b) : ret = ret*a ret = ret%m return ret def IsPrime(n): if n == 1 : return FALSE i = 2 while i*i [EP019] 윤년 1901년 1월부터 2000년 12월까지 중에서 1일이 일요일인 달의 갯수를 구하는 문제. 윤년을 구하는 조건이 주어지고, 그 조건만 잘 써 주고, mod 7을 이용하면 요일을 구할 수 있다. // leap_year.cpp : Defines the entry point for the console application. // /* http://projecteuler.net *____________________________________________________________________ Problem 19 14 June 2002 You are given the following information, but you may prefer to do some research for yourself. .. [EP 074] f(145) = 1! + 4! + 5! = 145 정수에 대해서 그 정수를 십진수로 표현했을 때, 각 자리수의 계승(팩토리얼)의 합을 취하는 조작이 있다. 어떤 정수에서 시작하더라도 이 조작을 반복하면 어떤 루프를 돌게 된다. 이 루프는 링크에서 말한 것 밖에 없다고 한다. 이걸 알고서... 1000000보다 작은 정수 중에서 그 정수에서부터 시작하여, 조작을 반복하여 만들어지는 수의 집합의 갯수가 60개인 것들의 갯수를 구하란다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=74 # factorial list from functools import lru_cache factorial = [1] # 0! = 1 for i in range(1, 10): fact.. 1/1, 1/2, ... 1/999 의 순환소수 표현 프로젝토 오일러 26번 문제를 오랜만에 다시 풀었다. 중간결과로 n=1부터 1000 이하까지의 1/n 의 순환소수 표현을 구했다. 순환마디의 길이가 커지는 숫자들은 거의 소수로 보이고, 이 숫자들에 대해서 순환마디의 길이는 n-1 이다. 나아가 오일러파이함수(totient)와 관련이 있음. (아래 see also 1, 2) see also : 0. 관련파이썬코드 1. http://daewonyoon.pythonanywhere.com/fraction/ 2. 순환마디에대한수학적논의 3. mathnet의 관련항목 괄호로 감싼 것이 반복되는 순환마디이다. 1/1 = 1.(0) 1/2 = 0.5(0) 1/3 = 0.(3) 1/4 = 0.25(0) 1/5 = 0.2(0) 1/6 = 0.1(6) 1/7 = 0.(14.. [EP 023] 두 과잉수의 합으로 나타낼 수 없는 모든 수의 합 완전수는 자신보다 작은 약수의 합이 자신과 같은 수이다. 예로는 6, 28 등이 있다. 과잉수는 이 합이 자신보다 큰 것을 말한다. 두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은? 자신을 포함하는 모든 약수의 합, 즉 약수함수가 곱셈적이라는 성질 때문에 재귀함수를 만들거나 캐시리스트를 만드는 방식으로 "쪼개서" 문제를 해결하는 전략을 쓸 수 있다. 아래코드는 s 라는 리스트에 약수함수값을 저장하여 n의 약수함수값을 s[n] 으로 가져올 수 있고, n = p q 일 때에, 가장 작은 소수인수를 만나면, s(n) = s[p] s[q] 라는 성질을 이용하여, 차례대로 s 리스트를 채우는 방식으로 문제를 풀어본 것이다. # PROJECT EULER # PROBLEM 23 def s_f(n): """.. [EP 050] 연속된소수의합이 다시 소수 무식한 방법으로 푼다. 루프를 빠져나오는 조건을 잘 줘야 빨리 끝난다. 소수를 구할 때, 나눌 수가 소수후보의 제곱근보다 크다면 빠져나오라는 조건을 빼면 시간이 하염없이 걸리고, 연속된소수의 합이 다시 소수인 모든 수를 구하는 것이 아니고, 그 소수 갯수의 최대값을 구한다는 조건을 for 루프에 잘 적용하면 또 시간을 더 단축할 수 있다. 물론 깔끔함은 훼손되지. /* * http://projecteuler.net/index.php?section=problems&id=50 Problem 50 15 August 2003 The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is t.. [수학] 페르마 소정리 이해를 위한 장난 rsa를 주제로 한 오일러 프로젝트 문제를 풀다가, 페르마 소정리에 대해서 감이 잘 안 와서 엑셀로 계산을 시켜봤다. p = 3, q = 7 인 상당히 간단한 경우의 계산이다. 엑셀이 상당한 프로그래밍 시간을 줄여주기는 하는데, 내 입맛에 딱 맞춰 결과를 보기에는 아직 익숙하지가 않아서 좀 고달픈 구석이 있다. 이전 1 다음
