Prime Sum of Nth Power Program

January 19, 2023

Prime Sum of N^th 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.

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

Code in C++

Code in C

Code in C++

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;
}

Code in C

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

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.

Code in C++

Code in C

Code in C++

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;
}

Code in C

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

Tokens in C

Size of Operators

Conditional statement Program in C

fseek() in C

pointer v/s array in C

Method 3 :

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

Code in C++

Code in C

Code in C++

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;
}

Code in C

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

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

Prime Sum of Nth Power Program