Count of ways to represent N as sum of a prime number and twice of a square | Python3 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 ; 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 math NEW_LINE n = 500000 - 2 NEW_LINE v = [ ] NEW_LINE def sieveoferanthones ( ) : NEW_LINE INDENT prime = [ 1 ] * ( n + 1 ) NEW_LINE for i in range ( 2 , int ( math . sqrt ( n ) ) + 1 ) : NEW_LINE INDENT if ( prime [ i ] != 0 ) : NEW_LINE INDENT for j in range ( i * i , n + 1 , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT for i in range ( 2 , n ) : NEW_LINE INDENT if ( prime [ i ] != 0 ) : NEW_LINE INDENT v . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def numberOfWays ( n ) : NEW_LINE INDENT count = 0 NEW_LINE j = 1 NEW_LINE while ( 2 * ( pow ( j , 2 ) ) < n ) : NEW_LINE INDENT i = 1 NEW_LINE while ( v [ i ] + 2 <= n ) : NEW_LINE INDENT if ( n == v [ i ] + ( 2 * ( math . pow ( j , 2 ) ) ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT j += 1 NEW_LINE DEDENT print ( count ) NEW_LINE DEDENT sieveoferanthones ( ) NEW_LINE n = 9 NEW_LINE numberOfWays ( n ) NEW_LINE