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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #27: Quadratic primes
  4. Discussions

Project Euler #27: Quadratic primes

Problem
Submissions
Leaderboard
Discussions

Sort 35 Discussions, By:

recency

Please Login in order to post a comment

  • nightbeggar
    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);
    
    ?>
    
    0|
    Permalink
  • rafael_rjsm
    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.

    0|
    Permalink
  • stefan_pricopie1
    7 months ago+ 0 comments

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

    -1|
    Permalink
  • s_mostafa_a
    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;
    }
    
    0|
    Permalink
  • yuvakiran821
    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]))
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy