// C++ program to get minimum step to reach 1  // under given constraints #include    using namespace std; // structure represent one node in queue struct data {  int val;  int steps;  data(int val int steps) : val(val) steps(steps)  {} }; // method returns minimum step to reach one int minStepToReachOne(int N) {  queue<data> q;  q.push(data(N 0));  // set is used to visit numbers so that they  // won't be pushed in queue again  set<int> st;  // loop until we reach to 1  while (!q.empty())  {  data t = q.front(); q.pop();    // if current data value is 1 return its  // steps from N  if (t.val == 1)  return t.steps;  // check curr - 1 only if it not visited yet  if (st.find(t.val - 1) == st.end())  {  q.push(data(t.val - 1 t.steps + 1));  st.insert(t.val - 1);  }  // loop from 2 to sqrt(value) for its divisors  for (int i = 2; i*i <= t.val; i++)  {  // check divisor only if it is not visited yet  // if i is divisor of val then val / i will  // be its bigger divisor  if (t.val % i == 0 && st.find(t.val / i) == st.end())  {  q.push(data(t.val / i t.steps + 1));  st.insert(t.val / i);  }  }  }  } // Driver code to test above methods int main() {  int N = 17;  cout << minStepToReachOne(N) << endl;  } 

// Java program to get minimum step to reach 1  // under given constraints  import java.util.*; class GFG {  // structure represent one node in queue  static class data  {   int val;   int steps;  public data(int val int steps)   {  this.val = val;  this.steps = steps;  }    };  // method returns minimum step to reach one  static int minStepToReachOne(int N)  {   Queue<data> q = new LinkedList<>();   q.add(new data(N 0));   // set is used to visit numbers so that they   // won't be pushed in queue again   HashSet<Integer> st = new HashSet<Integer>();   // loop until we reach to 1   while (!q.isEmpty())   {   data t = q.peek(); q.remove();     // if current data value is 1 return its   // steps from N   if (t.val == 1)   return t.steps;   // check curr - 1 only if it not visited yet   if (!st.contains(t.val - 1))   {   q.add(new data(t.val - 1 t.steps + 1));   st.add(t.val - 1);   }   // loop from 2 to Math.sqrt(value) for its divisors   for (int i = 2; i*i <= t.val; i++)   {   // check divisor only if it is not visited yet   // if i is divisor of val then val / i will   // be its bigger divisor   if (t.val % i == 0 && !st.contains(t.val / i) )   {   q.add(new data(t.val / i t.steps + 1));   st.add(t.val / i);   }   }   }  return -1; }  // Driver code  public static void main(String[] args)  {   int N = 17;   System.out.print(minStepToReachOne(N) +'n');  } }  // This code is contributed by 29AjayKumar 

# Python3 program to get minimum step # to reach 1 under given constraints # Structure represent one node in queue class data: def __init__(self val steps): self.val = val self.steps = steps # Method returns minimum step to reach one def minStepToReachOne(N): q = [] q.append(data(N 0)) # Set is used to visit numbers # so that they won't be pushed # in queue again st = set() # Loop until we reach to 1 while (len(q)): t = q.pop(0) # If current data value is 1 # return its steps from N if (t.val == 1): return t.steps # Check curr - 1 only if # it not visited yet if not (t.val - 1) in st: q.append(data(t.val - 1 t.steps + 1)) st.add(t.val - 1) # Loop from 2 to Math.sqrt(value) # for its divisors for i in range(2 int((t.val) ** 0.5) + 1): # Check divisor only if it is not # visited yet if i is divisor of val # then val / i will be its bigger divisor if (t.val % i == 0 and (t.val / i) not in st): q.append(data(t.val / i t.steps + 1)) st.add(t.val / i) return -1 # Driver code N = 17 print(minStepToReachOne(N)) # This code is contributed by phasing17 

// C# program to get minimum step to reach 1  // under given constraints  using System; using System.Collections.Generic; class GFG {  // structure represent one node in queue  class data  {   public int val;   public int steps;  public data(int val int steps)   {  this.val = val;  this.steps = steps;  }  };  // method returns minimum step to reach one  static int minStepToReachOne(int N)  {   Queue<data> q = new Queue<data>();   q.Enqueue(new data(N 0));   // set is used to visit numbers so that they   // won't be pushed in queue again   HashSet<int> st = new HashSet<int>();   // loop until we reach to 1   while (q.Count != 0)   {   data t = q.Peek(); q.Dequeue();     // if current data value is 1 return its   // steps from N   if (t.val == 1)   return t.steps;   // check curr - 1 only if it not visited yet   if (!st.Contains(t.val - 1))   {   q.Enqueue(new data(t.val - 1 t.steps + 1));   st.Add(t.val - 1);   }   // loop from 2 to Math.Sqrt(value) for its divisors   for (int i = 2; i*i <= t.val; i++)   {   // check divisor only if it is not visited yet   // if i is divisor of val then val / i will   // be its bigger divisor   if (t.val % i == 0 && !st.Contains(t.val / i) )   {   q.Enqueue(new data(t.val / i t.steps + 1));   st.Add(t.val / i);   }   }   }  return -1; }  // Driver code  public static void Main(String[] args)  {   int N = 17;   Console.Write(minStepToReachOne(N) +'n');  } } // This code is contributed by 29AjayKumar 

<script> // Javascript program to get minimum step // to reach 1 under given constraints  // Structure represent one node in queue  class data  {  constructor(val steps)  {  this.val = val;  this.steps = steps;  } } // Method returns minimum step to reach one  function minStepToReachOne(N) {  let q = [];  q.push(new data(N 0));     // Set is used to visit numbers   // so that they won't be pushed   // in queue again   let st = new Set();     // Loop until we reach to 1   while (q.length != 0)   {   let t = q.shift();    // If current data value is 1  // return its steps from N   if (t.val == 1)   return t.steps;     // Check curr - 1 only if   // it not visited yet   if (!st.has(t.val - 1))   {   q.push(new data(t.val - 1   t.steps + 1));   st.add(t.val - 1);   }     // Loop from 2 to Math.sqrt(value)   // for its divisors   for(let i = 2; i*i <= t.val; i++)   {     // Check divisor only if it is not  // visited yet if i is divisor of val  // then val / i will be its bigger divisor   if (t.val % i == 0 && !st.has(t.val / i))   {   q.push(new data(t.val / i  t.steps + 1));   st.add(t.val / i);   }   }   }  return -1; } // Driver code  let N = 17;  document.write(minStepToReachOne(N) + '  
');  // This code is contributed by rag2127 </script>