Problem 27

Projekt Euler w Ruby
1

Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

2

Mam dwa rozwiązania. Pierwsze to bez optymalizacji. Drugie jest zoptymalizowane.

Pierwsze:

[code=ruby]#!/usr/bin/env ruby
N = 999
M = 999

def formula(n, a, b)
nn+an+b
end

def prime?(x)
!((2…Math.sqrt(x).ceil).detect { |d| x%d == 0 }) if x >= 2
end

t = [nil, nil, 0]

(-N).upto(N) do |a|
1.upto(M) do |b|
n = 0
n += 1 while prime?(formula(n, a, b))
t = [t, [a, b, n]].max { |u, v| u[2] <=> v[2] }
end
if a.abs%10 == 0 || a == N
STDOUT.print "a=#{t[0].to_s.ljust(4)}, "
STDOUT.print "b=#{t[1].to_s.ljust(4)}, "
STDOUT.print "n=#{(t[2]-1).to_s.ljust(6)} "
STDOUT.print “(a=#{a.to_s.ljust(4)})\r”
STDOUT.flush
end
end
STDOUT.puts
STDOUT.puts “Answer: #{t[0]*t[1]}”[/code]
Drugie:

[code=ruby]#!/usr/bin/env ruby
N = 999
M = 999

$cache = { }

def formula(n, a, b)
nn+an+b
end

def prime?(x)
unless $cache[x]
if x >= 2 && !((2…Math.sqrt(x).ceil).detect { |d| x%d == 0 })
$cache[x] = true
end
else
true
end
end

t = [nil, nil, 0]

(-N).step(N, 2) do |a|

b = 2 to n <= 2

3.step(M, 2) do |b|
n = 0
n += 1 while prime?(formula(n, a, b))
t = [t, [a, b, n]].max { |u, v| u[2] <=> v[2] }
end
if a.abs%10 == 1 || a == N
STDOUT.print "a=#{t[0].to_s.ljust(4)}, "
STDOUT.print "b=#{t[1].to_s.ljust(4)}, "
STDOUT.print "n=#{(t[2]-1).to_s.ljust(6)} "
STDOUT.print “(a=#{a.to_s.ljust(4)})\r”
STDOUT.flush
end
end
STDOUT.puts
STDOUT.puts “Answer: #{t[0]*t[1]}”[/code]

3

Moje rozwiązanie po optymalizacji, w wersji pierwotnej obliczenia zajmowały ~18s :(. Teraz 3s(Procesor: 1.86 GHz).

[code=ruby]require ‘libprime’

started_at = Time.now.to_f
product = 0
max = 0
limit = 1000
0.upto(limit) { |b| # b must be prime(for n = 0), all primes are positive
next if !b.prime?
(-1limit).upto(limit) { |a|
next if !(1+a+b).prime? # This must be prime for n = 1
next if (a+b) < 0
b.times { |n|
number = nn + an + b
if n > max
max = n
product = ab
end
break if !number.prime?
}
}
}
puts “Product for max number of primes: #{product}”
puts “Took #{Time.now.to_f - started_at} s.”[/code]
Biblioteka libprime.rb:

[code=ruby]class Integer
def prime?
if self <2
return false
elsif self < 4
return true
elsif self % 2 == 0
return false
elsif self < 9
return true
elsif self % 3 == 0
return false
else
r = (self**0.5).floor
f = 5
f.step r,6 do |g|
if self % g == 0
return false
end
if self % (g + 2) == 0
return false
end
end
return true
end
end
end

class Prime
def initialize
@last_prime = nil
end

def succ
if @last_prime.nil?
@last_prime = 2
return 2
else
i = @last_prime + 1
i += 1 if i % 2 == 0
while not i.prime?
i += 2
end
@last_prime = i
return i
end
end
alias next succ
def each
loop do
yield succ
end
end
end[/code]

4

Moje podejście podobne do powyższego. Trochę “brute force”, ale chyba o to chodziło “poecie” :slight_smile:

[code=ruby]require ‘prime’
champion = 0
aa = 0
bb = 0
all_primes = []
Prime.each(1000) do |e|
all_primes << e
end

number of primes generated by formula:

def nopgbf(a,b)
set_of_primes = []
0.upto(1000) do |cc|
n = cc.to_i
result = nn+an+b
if result.prime?
set_of_primes << result
else
break
end
end
set_of_primes.size
end

(-1000).upto(1000) do |a|
all_primes.each do |b|
if nopgbf(a,b) > champion
champion = nopgbf(a,b)
aa = a
bb = b
end
end
end
puts “Formule (n*n + #{aa}n + #{bb}) produces #{champion} primes. Result = #{aabb}”[/code]
W około 6 sekund.