Euler Solution 46

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 46

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

Ruby by tomchristmas

Runtime: 3.411s (on aglaope). A *marked* improvement on the previous version! All I did was rewrite the prime generator so that it didn't re-generate all of the primes every time and 'bingo-bongo' (as Brian Stephenson would say), you've got a 15-fold improvement in execution!

def prime_list(pl, max)
    p = pl
    min = pl.nitems > 0 ? pl.last : 2

    min.upto(max){|x|
      c = 0
      prime = true

      while c < p.length && prime
        prime = false if (x % p[c] == 0)
        c += 1
      end
      p << x if prime
   }

   return p
end

def is_composite?(num)
    comp = false

    2.upto(num/2){|n|
      comp = true if num % n == 0
    }

    return comp
end

c = 1
composite_found = false
pl = []

while !composite_found
      if is_composite?(c)

         goldbach_found = false
         pl = prime_list(pl.dup, c)

         pl.each{|p|
            d = Math.sqrt((c - p)/2.0)
            dd = (d.floor == d.ceil) ? (c - p) : 0
            if c == p + dd
               goldbach_found = true
               puts "#{c} = #{p} + 2 x #{d}^2"
            end
         }
         composite_found = true if !goldbach_found
      end
      c += 2 if !composite_found
end

puts c 

Python by Althalus

Runtime: 4.1s

import primeFunctions

limit = 10000
primes = primeFunctions.genPrimes(limit)
squares = [x*x*2 for x in range(1,100) if x*x < limit] 

for x in range(3,limit,2):
 if x not in primes:
  theanswer = True
  for prime in primes:
   if prime >= x: break
   if (x - prime) in squares:
       theanswer = False
  if theanswer:
    print x
    break
Personal tools