Project Euler 1~10

仕事が暇な時に頭の体操がてらボチボチやってみてます。
「よっしゃ出来たオレ天才」とか思ってたら、他の人は1行とかで終わらせててクソワロタ。
ワロタ。。。

## Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

```python
def hoge(num):
    ans = 0
    for n in xrange(1, num):
        if n % 3 == 0 or n % 5 == 0:
            ans += n
    return ans

print hoge(1000)
```

## Problem 2 「偶数のフィボナッチ数」
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

```python
def hoge(num):
    x = 1
    y = 2
    ans = 0
    while y <= num:
        if y % 2 == 0:
            ans += y
        y = x + y
        x = y - x
    return ans

hoge(4000000)
```

## Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.

```python
def hoge(num):
    x = 2
    soinsu = set()
    while 1:
        if num < 2:
            return None
        if num == x:
            soinsu.add(x)
            break
        elif num % x == 0:
            soinsu.add(x)
            num = num / x
        else:
            x += 1
    return max(soinsu)

print hoge(600851475143)
```

## Problem 4 「最大の回文積」
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

```python
def hoge(num):
    min = 10 ** (num - 1)
    max = 10 ** num -1
    ans = 0
    for x in xrange(min, max):
        for y in xrange(min, max):
            if str(x * y) == str(x * y)[::-1]:
                if (x * y) > ans:
                    ans = x * y
    return ans

print hoge(3)
```

## Problem 5 「最小の倍数」
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

```python
def hoge(num):
    ans = num
    while 1:
        flg = True
        for x in xrange(1, num+1):
            if ans % x != 0:
                flg = False
                break
        if flg == True:
            break
        else:
            ans += num
    return ans

print hoge(20)
```

## Problem 6 「二乗和の差」
最初の10個の自然数について, その二乗の和は,
1^2 + 2^2 + ... + 10^2 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)^2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

```python
def hoge(num):
    return (sum(xrange(1, num+1)) ** 2) - sum([ x ** 2 for x in xrange(1, num+1) ])

print hoge(100)
```

## Problem 7 「10001番目の素数」
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.

```python
def hoge(num):
    cnt = 0
    x = 2
    while 1:
        flg = True
        for y in xrange(2, x):
            if x % y == 0:
                flg = False
                break
        if flg == True:
            cnt += 1
            if num == cnt:
                break
        x += 1
    return x

print hoge(10001)
```

## Problem 8 「数字列中の最大の積」
次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.
(省略：1000桁の数字はプログラム参照)
この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
EX 6桁の数123789から5個の連続する数字を取り出す場合, 1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.

```python
numbers = '''
    73167176531330624919225119674426574742355349194934
    96983520312774506326239578318016984801869478851843
    85861560789112949495459501737958331952853208805511
    12540698747158523863050715693290963295227443043557
    66896648950445244523161731856403098711121722383113
    62229893423380308135336276614282806444486645238749
    30358907296290491560440772390713810515859307960866
    70172427121883998797908792274921901699720888093776
    65727333001053367881220235421809751254540594752243
    52584907711670556013604839586446706324415722155397
    53697817977846174064955149290862569321978468622482
    83972241375657056057490261407972968652414535100474
    82166370484403199890008895243450658541227588666881
    16427171479924442928230863465674813919123162824586
    17866458359124566529476545682848912883142607690042
    24219022671055626321111109370544217506941658960408
    07198403850962455444362981230987879927244284909188
    84580156166097919133875499200524063689912560717606
    05886116467109405077541002256983155200055935729725
    71636269561882670428252483600823257530420752963450
'''

def hoge(numbers, num):
    numbers = numbers.replace(' ', '').replace('\n', '')
    ans = 0
    for i in xrange(len(numbers) - num + 1):
        x = list(numbers[i:(i+num)])
        x = [ int(y) for y in x ]
        tmp_ans = 1
        for z in x:
            tmp_ans *= z
        if ans < tmp_ans:
            ans = tmp_ans
    return ans

print hoge(numbers, 13)
```

## Problem 9 「特別なピタゴラス数」
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

```python
def hoge(num):
    for a in xrange(1, num):
        for b in xrange(1, num):
            if a + b > num -1:
                break
            c2 = a ** 2 + b ** 2
            for c in xrange(1, c2/2):
                if c ** 2 > c2:
                    break
                elif c ** 2 == c2:
                    if a ** 2 + b ** 2 == c ** 2 and a + b + c == num:
                        return a * b * c

print hoge(1000)
```

## Problem 10 「素数の和」
10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.

```python
def hoge(num):
    sosu = []
    for x in xrange(2, num+1):
        flg = True
        for y in sosu:
            if x % y == 0:
                flg = False
                break
        if flg == True:
            for y in xrange(max(sosu)+1 if sosu else 2, x/2+1):
                if x % y == 0:
                    flg = False
                    break
            if flg == True:
                sosu.append(x)
    return sum(sosu)

print hoge(2000000)
```