Project Euler #27: Quadratic primes Discussions |

Sort 35 Discussions, By:

3 months 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);

?>

5 months ago+ 0 comments

As for "n=0" the value of n^2+an+b must be prime, b will be prime, so it is enough to iterate over every prime b between [-n,n], obtained by the sieve of Eratosthenes.

7 months ago+ 0 comments

Although the problem clearly says , the tests results are set on . Hope that helps

2 years ago+ 0 comments

Brute force works here :

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define debug(x) cout << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
inline ll Mod(ll x, ll mod) { return x % mod >= 0 ? x % mod : x % mod + mod; }

vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

void find_primes(int n)
{
    for (int i = 51; i <= n; i += 2)
    {
        bool flag = 0;
        for (int j : primes)
        {
            if (j * j > i)
                break;
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if (!flag)
            primes.emplace_back(i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    primes.reserve(20000);
    find_primes(24000);
    int n;
    cin >> n;
    int ansa = 0, ansb = 0, MAX = 0;
    for (int a = -n; a <= n; a++)
    {
        for (int b = -n; b <= n; b++)
        {
            int cnt = 0;
            while (binary_search(all(primes), cnt * cnt + cnt * a + b))
            {
                cnt++;
            }
            if (MAX < cnt)
            {
                ansa = a;
                ansb = b;
                MAX = cnt;
            }
        }
    }
    cout << ansa << " " << ansb;
}

3 years ago+ 1 comment

its passed all cases but still need to reduce for efficiency :)

from math import sqrt
from itertools import count,islice
def primes(n):
    numbers=set(range(n-1,1,-1))
    prime=[]
    while numbers:
        k=numbers.pop()
        prime.append(k)
        numbers.difference_update(set(range(k*2,n,k)))
    return prime
def check(n):
    return n>1 and all(n%i for i in islice(count(2),int(sqrt(n))-1))
def conset(ab):
    a,b=ab[0],ab[1]
    for i in count():
        n=i*(i+a)+b
        if not check(n):
            return i
n=int(input())
b=primes(n)
a=list(range(-n,n+1,2)) if n&1 else list(range(-n+1,n,2))
s=max(((i,j) for i in a for j in b),key=conset)
print(str(s[0]),str(s[1]))

Load more conversations