Maximum Primes whose sum is equal to given N
Given a positive integer N > 1. Find the maximum count of prime numbers whose sum is equal to the given N.
Examples:
Input : N = 5
Output : 2
Explanation : 2 and 3 are two prime numbers whose sum is 5.
Input : N = 6
Output :3
Explanation : 2, 2, 2 are three prime numbers whose sum is 6.
For the maximum number of primes whose sum is equal to given n, prime numbers must be as small as possible. So, 2 is the smallest possible prime number and is an even number. The next prime number is greater than 2 in 3 which is odd. So, for any given n there are two conditions, either n will be odd or even.
- Case 1: n is even, In this case, n/2 will be the answer (n/2 number of 2 will result in the sum of n).
- Case 2: n is odd, In this case, floor(n/2) will be the answer ((n-3)/2 number of 2, and one 3 will result in the sum of n).
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find max count of primes int maxPrimes( int n) { // if n is even n/2 is required answer // if n is odd floor(n/2) = (int)(n/2) is required answer return n / 2; } // Driver Code int main() { int n = 17; cout << maxPrimes(n); return 0; } |
Java
// Java program for above approach class GFG { // Function to find max count of primes static int maxPrimes( int n) { // if n is even n/2 is required answer // if n is odd floor(n/2) = (int)(n/2) // is required answer return n / 2 ; } // Driver Code public static void main(String[] args) { int n = 17 ; System.out.println(maxPrimes(n)); } } // This code is contributed // by Code_Mech |
Python3
# Python3 program for above approach # Function to find max count of primes def maxPrmimes(n): # if n is even n/2 is required answer # if n is odd floor(n/2) = (int)(n/2) # is required answer return n / / 2 # Driver code n = 17 print (maxPrmimes(n)) # This code is contributed # by Shrikant13 |
C#
// C# program for above approach using System; class GFG { // Function to find max count of primes static int maxPrimes( int n) { // if n is even n/2 is required answer // if n is odd floor(n/2) = (int)(n/2) // is required answer return n / 2; } // Driver Code public static void Main() { int n = 17; Console.WriteLine(maxPrimes(n)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP program for above approach // Function to find max count of primes function maxPrimes( $n ) { // if n is even n/2 is required answer // if n is odd floor(n/2) = (int)(n/2) is required answer return (int)( $n / 2); } // Driver Code $n = 17; echo maxPrimes( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program for above approach // Function to find max count of primes function maxPrimes(n) { // if n is even n/2 is required answer // if n is odd floor(n/2) = (int)(n/2) is required answer return parseInt(n / 2); } // Driver Code var n = 17; document.write( maxPrimes(n)); </script> |
Output:
8
Time Complexity: O(1)
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us