본문 바로가기
[파이썬]프로젝트 오일러 #7 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요. n = 2**20 primes = [] #소수를 담을 list table = [False, False] + [True]*(n-1) for i in range(2, n+1): if table[i]: primes.append(i) for j in range(2*i, n+1, i): table[j] = False print(primes[10000]) #10001번째 값을 꺼낸다. 소수를 구하는 방법은 프로젝트 오일러 5번 문제에 사용했던 table을 만들고 소수의 배수를 하나씩 False로 지워나가는 방식을 사용하였다. 문제점이 있다면 에라토스테네스의 체를 사용하기 위해 맨처음 .. 2022. 9. 27.
[파이썬]프로젝트 오일러 #5 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 최소공배수를 구해보면서 위 사진에 나온것과 같은 규칙을 얻었다. n = 20 multiple = 1 a = [False, False] + [True]*(n-1) #소수를 구하는 알고리즘(0~n까지의 배열 체를 만드는 과정) for i in range(2, n+1): if a[i]: #i가 소수라면 multiple = multiple*i primebreak = True for k in range(n, 2, -1): for l in range(2, n): if (k==i**l): multiple = multiple*(i**(l-1)) primeb.. 2022. 9. 25.
[파이썬]프로젝트 오일러 #4 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다. 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? a = [] for i in range(1, 1000): for j in range(1, 1000): num = i * j if num >= 100000: if (int(str(num)[0])== int(str(num)[5])) and (int(str(num)[1])== int(str(num)[4])) and (int(str(num)[2])== int(str(num)[3])): a.append(num) print(max(a)) 1학기때 코딩도.. 2022. 9. 18.
[파이썬]프로젝트 오일러 #3 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요. n = 600851475143 prime = [] i = 2 while n>=i: #마지막으로 나눠진 나머지가 나누는 숫자보다 작아지면 계산을 그만하기위한 반복문 if n%i == 0: prime.append(i) n = n//i else: i += 1 list(set(prime)) print(prime[-1]) 600851475143란 숫자 대신 생각하기 쉬운 140이란 숫자를 가지고 알고리즘을 구상했다. n을 2부터 시작해 나눠질때까지 나누고 더이상 나눠지지 않으면 1식 늘.. 2022. 9. 18.
[파이썬]프로젝트 오일러 #2 피보나치수열에서 400만 이하이면서 짝수인 항의 합 *피보나치 수열 :첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 a = 1 b = 2 pibo = 0 sum = 2 while pibo 2022. 9. 12.
[파이썬]프로젝트 오일러 #1 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더한 값 sum = 0 #합을 저장할 변수 for n in range(1, 1000): if (n%3 == 0) or (n%5==0): #1~1000까지의 숫자중 3의 배수거나 5의 배수면 sum변수에 숫자를 더한다 sum += n print(sum) 답 : 233168 처음엔 3의 배수와 5의 배수를 다른 명령문으로 따로 더하고 중복되는 15의 배수를 다시 빼줘야하나라는 생각이 제일 먼저 들었다. 문제를 다시보니 3 "또는" 5의 배수 라고 적혀져 있어서 그 문장을 그대로 코드로 만들었다. 하지만 처음 방식대로 코드를 실행하면 0.00064 sec가 걸리고 후자의 방식으로 코드를 실행하면 0.00120 sec가 걸린다........ 2022. 9. 12.

티스토리툴바