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.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #46: Goldbach's other conjecture
  4. Discussions

Project Euler #46: Goldbach's other conjecture

Sort by

recency

|

18 Discussions

|

  • upadhyaysmriti21
     + 0 comments

    My code shows incorrect answer for test case 3 and 4. Can someone help me out on this?

    import math
x = (5*(10**5))+1
prime_list = [0 for i in range(x)]
prime_list[0] = prime_list[1]= 1
for i in range(2, ((5*(10**5))//2)+1):
    if prime_list[i] == 0:
        for j in range(i**2, ((5*(10**5))//2)+1, i):
            prime_list[j] = 1
prime = [i for i in range(x) if prime_list[i]==0]

for i in range(int(input())):
    n = int(input().strip())
    count = 0
    if n<=2 or n% 2==0:
        print(0)
    else:
        index = 0
        p = prime[0]
        while p < n:
            ans1 = (n-p)/2
            ans2 = math.modf(math.sqrt(ans1))
           
            if ans2[0] == 0.0:
                count+=1
            index+=1
            p = prime[index]
            
        print(count)

  • vijaykumarredd52
     + 0 comments

    C#

    using System;

    public class Solution { private static bool[] prime = null;

    public static void Main(string[] args)
{
    int numberOfTestCases = int.Parse(Console.ReadLine());
    GeneratePrimes();

    for (int i = 0; i < numberOfTestCases; i++)
    {
        int res = 0;
        int n = int.Parse(Console.ReadLine());
        for (int j = 2; j <= n; j++)
        {
            if (prime[j])
            {
                int diff = n - j;
                if (diff % 2 == 0 && IsPerfectSquare(diff / 2))
                    res += 1;
            }
        }
        Console.WriteLine(res);
    }
}

public static bool IsPerfectSquare(int input)
{
    int root = (int)Math.Sqrt(input);
    return input == root * root;
}

public static void GeneratePrimes()
{
    int limit = 1000000;
    prime = new bool[limit + 1];
    prime[2] = true;
    prime[3] = true;
    int root = (int)Math.Ceiling(Math.Sqrt(limit));

    // Sieve of Atkin for prime number generation
    for (int x = 1; x < root; x++)
    {
        for (int y = 1; y < root; y++)
        {
            int n = 4 * x * x + y * y;
            if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                prime[n] = !prime[n];

            n = 3 * x * x + y * y;
            if (n <= limit && n % 12 == 7)
                prime[n] = !prime[n];

            n = 3 * x * x - y * y;
            if ((x > y) && (n <= limit) && (n % 12 == 11))
                prime[n] = !prime[n];
        }
    }

    for (int i = 5; i <= root; i++)
    {
        if (prime[i])
        {
            for (int j = i * i; j < limit; j += i * i)
            {
                prime[j] = false;
            }
        }
    }
}

    }

  • nkosi9976
     + 0 comments

    this is the happy_coder solution in python ,to those interested in the python version of the solution

    import math

def main():
    numberOfTestCases = int(input())
    generatePrimes()

    for i in range(numberOfTestCases):
        res = 0
        n = int(input())
        for j in range(2, n+1):
            if prime[j]:
                diff = n-j
                if diff % 2 == 0 and isPerfectSquare(diff//2):
                    res += 1
        print(res)

def isPerfectSquare(input):
    root = int(math.sqrt(input))
    return input == root * root

def generatePrimes():
    limit = 1000000
    global prime
    prime = [False] * (limit+1)
    prime[2] = True
    prime[3] = True
    root = int(math.ceil(math.sqrt(limit)))

    # Sieve of Atkin for prime number generation
    for x in range(1, root):
        for y in range(1, root):
            n = 4 * x * x + y * y
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                prime[n] = not prime[n]

            n = 3 * x * x + y * y
            if n <= limit and n % 12 == 7:
                prime[n] = not prime[n]

            n = 3 * x * x - y * y
            if x > y and n <= limit and n % 12 == 11:
                prime[n] = not prime[n]

    for i in range(5, root):
        if prime[i]:
            for j in range(i * i, limit, i * i):
                prime[j] = False

if __name__ == "__main__":
    main()

  • ankith_kumar68
     + 0 comments

    code in c:

    bool is_prime(int n){

    for (int i= 2; i<=sqrt(n); i++)  if(n%i == 0) return false;
return true;

    } int rec(int s){

    int n = 1;
      int count = 0;
      while (s-2*n*n > 1) {
          int num = s-2*n*n;
          if(is_prime(num)==true) count++;
          n++;
      }
return count;

    } int main() { 

    int t;
scanf("%d",&t);
while (t--) {
    int n;
    scanf("%d",&n);
    printf("%d\n",rec(n));
}
return 0;

    }

  • ketan_patel25
     + 0 comments

    JAva code 

    import java.io.*;
import java.util.*;

public class Solution {

     private static boolean[] prime = null;

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int numberOfTestCases = in.nextInt();
        generatePrimes();

        for(int i=0;i<numberOfTestCases;i++)
        {
            int res=0;
            int n = in.nextInt();
            for(int j=2;j<=n;j++)
            {
                if(prime[j])
                {
                    int diff=n-j;
                    if(diff%2==0 && isPerfectSquare(diff/2))
                        res+=1;
                }
            }
            System.out.println(res);
        }
    }

    public static boolean isPerfectSquare(int input)
    {
        int root = (int) Math.sqrt(input);
        return input == root * root;
    }

    public static void generatePrimes()
    {
        int limit = 1000000;
        prime = new boolean[limit+1];
        prime[2] = true;
        prime[3] = true;
        int root = (int) Math.ceil(Math.sqrt(limit));

        //Sieve of Atkin for prime number generation
        for (int x = 1; x < root; x++)
        {
            for (int y = 1; y < root; y++)
            {
                int n = 4 * x * x + y * y;
                if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                    prime[n] = !prime[n];

                n = 3 * x * x + y * y;
                if (n <= limit && n % 12 == 7)
                    prime[n] = !prime[n];

                n = 3 * x * x - y * y;
                if ((x > y) && (n <= limit) && (n % 12 == 11))
                    prime[n] = !prime[n];
            }
        }

        for (int i = 5; i <= root; i++)
        {
            if (prime[i])
            {
                for (int j = i * i; j < limit; j += i * i)
                {
                    prime[j] = false;
                }
            }
        }
    }
}