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
  • Apply
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #27: Quadratic primes
  4. Discussions

Project Euler #27: Quadratic primes

Contest ends in
Problem
Submissions
Leaderboard
Discussions

Sort 36 Discussions, By:

recency

Please Login in order to post a comment

  • vidush_rk11
    6 months ago+ 0 comments

    a little messy but solves all the testcases
    100/-points python3

    import itertools
    def isprime(x):
        if x%2==0:
            return False
        for i in range(3,int(x**0.5)+1,2):
            if x%i==0:
                return False
        return True
    
    n=int(input())
    max_consec=0
    solutions=[]
    for i in itertools.product(list(range(-n,n+1,1)),range(n+1)): #I didn't set the range of b through the negatives because for x=0 the exspression will become b which must be positive so only +values 
        primes=0
        x=0
        while True:
            abc=x**2+i[0]*x+i[1]
            if abc<0: #as our required number must be atleast positive
                break
            if not isprime(abc):
                break
            x+=1
            primes+=1
        if primes>max_consec:
            solutions.append(i)
            max_consec=primes
    print(*solutions[-1])
    
    0|
    Permalink
  • nightbeggar
    12 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
    1 year 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
    1 year ago+ 0 comments

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

    -1|
    Permalink
  • s_mostafa_a
    3 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
Load more conversations

Need Help?


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