We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #27: Quadratic primes
  4. Discussions

Project Euler #27: Quadratic primes

  • nightbeggar
     + 0 comments

    Brute forcing in PHP. Parameter a cannot be even because if it is, then n(n+a) will cycle through odd and even numbers so we won't get more than one consequitive prime. If a is odd, then n(n+a) will always be even which means b cannot be even either. So these two facts can speed up the search somewhat. 

    <?php

$MAX_N = 2000;
$sieve = array_fill(0, $MAX_N, 1);

function build_primes() {
    global $sieve, $MAX_N;
    
    // Use the Eratosphene's sieve
    for ($i = 2; $i < $MAX_N; $i++)
        if ($sieve[$i] != 0)
            for ($j = $i*$i; $j < $MAX_N; $j = $j+$i)
                $sieve[$j] = 0;
}

function max_primes(int $a, int $b) {
    global $sieve, $MAX_N;
    
    $count = $n = 0;
    while (true) {
        $r = $n*$n + $a*$n + $b;        
        if ($r < 0 || $r > $MAX_N || $sieve[$r] == 0) break;
        $count++;
        $n++;
    }
    
    return $count;
}

function find_ab(int $n) {
    $maxc = $maxa = $maxb = -1;
    for ($a = -$n; $a <= $n; $a++)
        for ($b = -$n; $b <= $n; $b++)
            if ($a % 2 != 0 && $b % 2 != 0) {
                $c = max_primes($a, $b);
                if ($c > 0 && $maxc < $c) {
                    $maxc = $c;
                    $maxa = $a;
                    $maxb = $b;
                }
            }
    return sprintf("%d %d", $maxa, $maxb);
}

$f = fopen("php://stdin", "r");
$line = fgets($f);
build_primes();
echo find_ab((int)$line);

?>