Project Euler #27: Quadratic primes Discussions |

2 years ago+ 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);

?>

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge