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.
importjava.io.*;importjava.util.*;publicclassSolution{privatestaticboolean[]prime=null;publicstaticvoidmain(String[]args){/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */Scannerin=newScanner(System.in);intnumberOfTestCases=in.nextInt();generatePrimes();for(inti=0;i<numberOfTestCases;i++){intres=0;intn=in.nextInt();for(intj=2;j<=n;j++){if(prime[j]){intdiff=n-j;if(diff%2==0&&isPerfectSquare(diff/2))res+=1;}}System.out.println(res);}}publicstaticbooleanisPerfectSquare(intinput){introot=(int)Math.sqrt(input);returninput==root*root;}publicstaticvoidgeneratePrimes(){intlimit=1000000;prime=newboolean[limit+1];prime[2]=true;prime[3]=true;introot=(int)Math.ceil(Math.sqrt(limit));//Sieve of Atkin for prime number generationfor(intx=1;x<root;x++){for(inty=1;y<root;y++){intn=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(inti=5;i<=root;i++){if(prime[i]){for(intj=i*i;j<limit;j+=i*i){prime[j]=false;}}}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #46: Goldbach's other conjecture
You are viewing a single comment's thread. Return to all comments →
JAva code