Count of ways to represent N as sum of a prime number and twice of a square | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long int n = 500000 - 2 ; vector < long long int > v ; void sieveoferanthones ( ) { bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( long long int i = 2 ; i <= sqrt ( n ) ; i ++ ) { if ( prime [ i ] ) for ( long long int j = i * i ; j <= n ; j += i ) { prime [ j ] = false ; } } for ( long long int i = 2 ; i < n ; i ++ ) { if ( prime [ i ] ) v . push_back ( i ) ; } } void numberOfWays ( long long int n ) { long long int count = 0 ; for ( long long int j = 1 ; 2 * ( pow ( j , 2 ) ) < n ; j ++ ) { for ( long long int i = 1 ; v [ i ] + 2 <= n ; i ++ ) { if ( n == v [ i ] + ( 2 * ( pow ( j , 2 ) ) ) ) count ++ ; } } cout << count << endl ; } int main ( ) { sieveoferanthones ( ) ; long long int n = 9 ; numberOfWays ( n ) ; return 0 ; }