오일러 프로젝트 07

오일러 프로젝트 7번문제는 10001번째 소수를 찾는 문제이다.

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요.(http://euler.synap.co.kr/prob_detail.php?id=7)

오일러 프로젝트에서 처음으로 소수 판별 함수를 작성해볼 차례이다. 소수 판별 함수는 사실 알고리듬 자체는 매우 단순한데, 문제는 성능이다. 나이브하게 작성한 코드는 매우 느릴 수 밖에 없다.

  1. 2보다 작은 수는 0, 1 외에 음수이므로 이들은 모두 소수가 아니다.
  2. 2는 소수이다.
  3. 2보다 큰 경우 2, 3, 4… 등 자기 자신보다 작은 수로 나눠서 한 번이라도 나눠지면 소수가 아니다.
  4. 그 외에는 소수이다.

오일러 프로젝트 07 더보기

오일러 프로젝트 06

오일러 프로젝트 6번

1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).
1^2 + 2^2 + … + 10^2 = 385
1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).
(1 + 2 + … + 10)^2 = 55^2 = 3025
따라서 1부터 10까지 자연수에 대해 “합의 제곱”과 “제곱의 합” 의 차이는 3025 – 385 = 2640 이 됩니다. 그러면 1부터 100까지 자연수에 대해 “합의 제곱”과 “제곱의 합”의 차이는 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=6)

문제 그대로를 풀면 되겠다. 파이썬 코드는 다음과 같다.

print abs(sum(range(101)**2) - sum((x**2 for x in range(101))))

오일러 프로젝트 06 더보기

오일러 프로젝트 05

이번 문제는 최소공배수에  관한 내용이다. 문제는 다음과 같다.

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

 

 

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

오일러 프로젝트 05 더보기

오일러 프로젝트 04

오일러 프로젝트의 네 번째 문제는 대칭수와 관련된 문제이다. 대칭수는 139931 과 같이 앞에서부터 읽었을 때나 뒤에서부터 읽었을 때 같은 모양이 되는 수를 말한다. 문제는 다음과 같다.

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

 

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

 

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

오일러 프로젝트 04 더보기