Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample test cases

Approach

2.1.

Steps of algorithm

Implementation in C++

3.1.

Complexity Analysis

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Minimum steps to reduce N to a prime number by subtracting with its highest divisor

Q: Q1. Why is the Sieve of Eratosthenes important?

Answer: The Sieve of Eratosthenes is a simple and ancient algorithm for determining prime numbers up to a certain limit. It's one of the most time-saving methods for locating small prime numbers.

Q: Q2. Is it possible for negative numbers to be prime?

Answer: Negative integers cannot be prime according to the standard definition of prime for integers. Primes are integers greater than one with no positive divisors other than one and themselves. According to this definition, negative numbers are not considered.

Q: Q3. How do you check if a number is prime efficiently?

Answer: As we know, all number divisors exist in pairs. For example n = 50, all the divisors are (1, 50), (2, 25), (5, 10). We use this property to check for a prime number efficiently.

Author Sandeep kamila

Introduction

Problem Statement

We are given a number N. Our task is to find the minimum steps required to reduce a number 'N' to a prime number by subtracting with its highest divisor other than 1 and the N itself.

Sample test cases

Example 1:

Input: N = 14
Output: 1

Explanation
The highest divisor of 14 is 7, so N = (14 - 7) = 7 after subtracting with its highest divisor, 7 is a prime number.

Example 2:

Input: N= 28
Output: 2

Explanation
The highest divisor of 28 is 14, so N = (28 - 14) = 14 after subtracting with its highest divisor. Now, the highest divisor of 14 is 7, so N = (14 - 7) = 7 and 7 is a prime number.

Also see, Euclid GCD Algorithm

Approach

The idea is straightforward: we find the highest divisor of N, subtract N with it and increment the count of steps.

If the resulting number is prime after subtracting N with its highest divisor, print the number of steps required till now. Else repeat the above process with the resulting number in place of N.

Steps of algorithm

If the given number is prime, return 0 as it is already a prime number.
Create a variable mnm_steps = 0 to store the number of minimum steps required.
Initialise a variable i = 2 and run a while loop till N!=i.
Run another while loop inside the previous while loop. At every step, subtract N with its highest divisor and check the resulting number is prime or not.
If the resulting number is prime, return the value of mnm_steps.
Increment the value of i by 1.
Finally, return the value of mnm_steps.

Let's understand the above approach with an example:

Given number = 28

Initially mnm_steps = 0

The highest divisor of N = 28 is 14.
Subtract 28 with 14 and increment the value of mnm_steps by 1, N = (28 - 14) = 14 and mnm_steps = 1.
14 is not a prime number, so we repeat the above steps with N = 14.
The highest divisor of N = 14 is 7.
Subtract 14 with 7 and increment the value of mnm_steps by 1, N = (14 - 7) = 7 and mnm_steps = 2.
Now, 7 is a prime number. Return the value of mnm_steps = 2.

Implementation in C++

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

bool prime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }

    return true;
}

int minimum_steps(int N)
{
    if (N == 1)  // base case
        return -1;

    if (prime(N)) 
    {
        return 0;
    }

    else {
        int mnm_steps = 0;  // stores the minimum operations

        int i = 2;

        while (N != i)
        {
            while (N % i == 0)
            {
                int tmp = N;

                N = N - (tmp / i); // subtracting with highest divisor

                mnm_steps++;

                if (prime(N))
                    return mnm_steps;
            }

            i++;
        }

        return mnm_steps;
    }
}

int main()
{
    int N = 28;

    cout << minimum_steps(N);

    return 0;
}

Output:

Complexity Analysis

Time complexity: O(sqrt(n)), as we are running a loop sqrt(n) times for checking prime number.

Space complexity: O(1), as we are using constant extra space.

Frequently Asked Questions

Q1. Why is the Sieve of Eratosthenes important?

Answer: The Sieve of Eratosthenes is a simple and ancient algorithm for determining prime numbers up to a certain limit. It's one of the most time-saving methods for locating small prime numbers.

Q2. Is it possible for negative numbers to be prime?

Answer: Negative integers cannot be prime according to the standard definition of prime for integers. Primes are integers greater than one with no positive divisors other than one and themselves. According to this definition, negative numbers are not considered.

Q3. How do you check if a number is prime efficiently?

Answer: As we know, all number divisors exist in pairs. For example n = 50, all the divisors are (1, 50), (2, 25), (5, 10). We use this property to check for a prime number efficiently.

Run a loop from 2 to sqrt(n) times. If the given number is divisible by any number in this range, it is not a prime number. Else it is a prime number.

Key Takeaways

This article discussed the approach to finding the minimum steps required to reduce N to a prime number by subtracting with its highest divisor with examples and its implementation in C++.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!

Thank you for reading!