Prime Sum of Nth Power Program

Prime Sum of Nth Power Program

Here, in this page we will discuss the program, we are given two numbers x and n, find a number of ways x can be expressed as prime sum of n-th power of unique natural numbers.
Prime Sum of nth Power Program

Method Discussed :

  • Method 1: Using Naive Approach
  • Method 2 : Efficient way
  • Method 3 : Recursive way

Method 1 :

  • Iterate through all number starting from 1.
  • Now, for every number we check if it is prime then go further,
  • Otherwise skip that number.
  • For every number, we recursively try all greater numbers and if we are able to find sum,
  • We increment result
Run
#include <bits/stdc++.h>
using namespace std;

bool isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}
int power(int num, unsigned int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return power(num, n / 2) * power(num, n / 2);
    else
        return num * power(num, n / 2) * power(num, n / 2);
}
 
int checkRecursive(int x, int n, int curr_num = 1, int curr_sum = 0)
{

    int results = 0;
    
    int p;
    if(isprime(curr_num))
        p = power(curr_num, n);
        
    while (p + curr_sum < x) {
        results += checkRecursive(x, n, curr_num + 1, p + curr_sum);
        curr_num++;
        if(isprime(curr_num))
        p = power(curr_num, n);
    }
 
    if (p + curr_sum == x)
        results++;
 
    return results;
}
 
// Driver Code.
int main()
{
    int x = 10, n = 2;
    cout << checkRecursive(x, n);
    return 0;
}
Run
#include <stdio.h>
#include <math.h>

int isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}
int power(int num, unsigned int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return power(num, n / 2) * power(num, n / 2);
    else
        return num * power(num, n / 2) * power(num, n / 2);
}
 
int checkRecursive(int x, int n, int curr_num , int curr_sum )
{

    int results = 0;
    
    int p;
    if(isprime(curr_num))
        p = power(curr_num, n);
        
    while (p + curr_sum < x) {
        results += checkRecursive(x, n, curr_num + 1, p + curr_sum);
        curr_num++;
        if(isprime(curr_num))
        p = power(curr_num, n);
    }
 
    if (p + curr_sum == x)
        results++;
 
    return results;
}
 
int main()
{
    int x = 10, n = 2;
    printf("%d ", checkRecursive(x, n, 1, 0));
    return 0;
}

Output

1

Method 2 :

In this method we will discuss one of the efficient way for finding the prime sum of n-th power. For every such  numbers we first check all the number first it is prime or not.

Run
#include <bits/stdc++.h>
using namespace std;

int res = 0;

bool isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}

int checkRecursive(int num, int x, int k, int n)
{
    if (x == 0)
        res++;
     
    
    int r = (int)floor(pow(num, 1.0 / n));
 
    for (int i = k + 1; i <= r; i++) { if(!isprime(i)) continue; int a = x - (int)pow(i, n); if (a >= 0)
            checkRecursive(num, x - (int)pow(i, n), i, n);
    }
    return res;
}

int main()
{   
    int x=10, n=2;
    cout << checkRecursive(x, x, 0, n);
    return 0;
}
Run
#include <stdio.h>
#include <math.h>
int res = 0;

int isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}

int checkRecursive(int num, int x, int k, int n)
{
    if (x == 0)
        res++;
     
    
    int r = (int)floor(pow(num, 1.0 / n));
 
    for (int i = k + 1; i <= r; i++) { if(!isprime(i)) continue; int a = x - (int)pow(i, n); if (a >= 0)
            checkRecursive(num, x - (int)pow(i, n), i, n);
    }
    return res;
}

int main()
{
    printf("%d ",checkRecursive(10, 10, 0, 2));
    return 0;
}

Output

1

Method 3 :

In this method we will discuss the recursive approach for finding the required number of ways.

Run
#include <bits/stdc++.h>
using namespace std;

int res = 0;

bool isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}

int checkRecursive(int num, int x, int k, int n)
{
    if (x == 0)
        res++;
     
    
    int r = (int)floor(pow(num, 1.0 / n));
 
    for (int i = k + 1; i <= r; i++) { if(!isprime(i)) continue; int a = x - (int)pow(i, n); if (a >= 0)
            checkRecursive(num, x - (int)pow(i, n), i, n);
    }
    return res;
}

int main()
{   
    int x=10, n=2;
    cout << checkRecursive(x, x, 0, n);
    return 0;
}
Run
#include <stdio.h>
#include <math.h>

int isprime(int num){
    for(int i=2; i<sqrt(num); i++){
        if(num%i==0)
        return 0;
    }
    return 1;
}

int counter(int remainingSum, int power, int base){

    int result = 0;
    if(isprime(base))
    result = pow(base, power);
       
    if(remainingSum == result)
        return 1;
    if(remainingSum < result)
        return 0;
     
    int x = counter(remainingSum - result, power, base + 1);
    int y = counter(remainingSum, power, base+1);
    return x + y;
}
 
int getWays(int sum, int power) {
    return counter(sum, power, 1);
}
 
// Driver Code.
int main()
{
    int x = 10, n = 2;
    printf("%d ", getWays(x, n));
    return 0;
}

Output

1

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription