Count of interesting primes upto N | Java program to find the number of interesting primes up to N . ; Function to find all prime numbers ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries as true . A value in prime [ i ] will finally be false if i is Not a prime . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it ; Store all prime numbers ; Function to check if a number is perfect square or not ; To store all primes ; To store all interseting primes ; Store all perfect squares ; Store all perfect quadruples ; Store all interseting primes ; Return count of interseting primes ; Driver code
import java . util . * ; class GFG { static void SieveOfEratosthenes ( int n , HashSet < Integer > allPrimes ) { boolean [ ] prime = new boolean [ n + 1 ] ; Arrays . fill ( prime , true ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] ) allPrimes . add ( p ) ; } static int countInterestingPrimes ( int n ) { HashSet < Integer > allPrimes = new HashSet < Integer > ( ) ; SieveOfEratosthenes ( n , allPrimes ) ; HashSet < Integer > intersetingPrimes = new HashSet < Integer > ( ) ; Vector < Integer > squares = new Vector < Integer > ( ) , quadruples = new Vector < Integer > ( ) ; for ( int i = 1 ; i * i <= n ; i ++ ) { squares . add ( i * i ) ; } for ( int i = 1 ; i * i * i * i <= n ; i ++ ) { quadruples . add ( i * i * i * i ) ; } for ( int a : squares ) { for ( int b : quadruples ) { if ( allPrimes . contains ( a + b ) ) intersetingPrimes . add ( a + b ) ; } } return intersetingPrimes . size ( ) ; } public static void main ( String [ ] args ) { int N = 10 ; System . out . print ( countInterestingPrimes ( N ) ) ; } }