Count of ways to represent N as sum of a prime number and twice of a square | Java implementation to count the number of ways a number can be written as sum of prime number and twice a square ; Function to mark all the prime numbers using sieve ; Initially all the numbers are marked as prime ; Loop to mark the prime numbers upto the Square root of N ; Loop to store the prime numbers in an array ; Function to find the number ways to represent a number as the sum of prime number and square of a number ; Loop to iterate over all the possible prime numbers ; Increment the count if the given number is a valid number ; Driver Code ; Function Call
import java . util . * ; class GFG { static int n = 500000 - 2 ; static Vector < Integer > v = new Vector < > ( ) ; static void sieveoferanthones ( ) { boolean [ ] prime = new boolean [ n + 1 ] ; Arrays . fill ( prime , true ) ; for ( int i = 2 ; i <= Math . sqrt ( n ) ; i ++ ) { if ( prime [ i ] ) for ( int j = i * i ; j <= n ; j += i ) { prime [ j ] = false ; } } for ( int i = 2 ; i < n ; i ++ ) { if ( prime [ i ] ) v . add ( i ) ; } } static void numberOfWays ( int n ) { int count = 0 ; for ( int j = 1 ; 2 * ( Math . pow ( j , 2 ) ) < n ; j ++ ) { for ( int i = 1 ; v . get ( i ) + 2 <= n ; i ++ ) { if ( n == v . get ( i ) + ( 2 * ( Math . pow ( j , 2 ) ) ) ) count ++ ; } } System . out . print ( count + "NEW_LINE"); } public static void main ( String [ ] args ) { sieveoferanthones ( ) ; int n = 9 ; numberOfWays ( n ) ; } }