project-euler-python.py/problem 46 at master · bashareid/project-euler-python.py · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
"""

import math

def is_prime(num):
  for i in range(2, math.ceil(math.sqrt(num)) + 1):
    if num % i == 0:
      return False
  return True

number = 3

primes = [2]
while number  < 100000:
  if is_prime(number):
      primes.append(number)
  else:
    for prime in primes:
      if math.sqrt((number - prime) / 2 ) == int(math.sqrt((number - prime) / 2)):
      #(number  - prime) % 2 == 0:
        #print(number , prime)
        break
    else:
      print(number , prime)
      break
  number += 2