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.
Project Euler #27: Quadratic primes
Project Euler #27: Quadratic primes
+ 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); ?>
+ 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.
+ 0 comments Although the problem clearly says , the tests results are set on . Hope that helps
+ 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; }
+ 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
Sort 35 Discussions, By:
Please Login in order to post a comment