Given a number N (1 ? N ? 9×1018), the task is to find P and Q satisfying the equation N = P 2. Q where P and Q will be prime numbers.
Examples:
Input: N = 175
Output: P = 5, Q = 7Input: N = 2023
Output: P = 17, Q = 7
Method 1:
Approach: The problem can be solved based on the following idea:
As N = P2. Q then min(P, Q) ? 3?N .So we can find at least one of P and Q by doing iterations up to 3?N.
Follow the below steps to implement the idea:
- Let M be the maximum integer i among i = 1, 2, …, [ 3?N] that divides N (actually, M=P or Q).
- Check N/M divided by M . If it is divisible, P = M and Q = N/M2; otherwise, P = ?(N/M) and Q = M2.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find P and Qvoid solvePQ(int n){ // Taking long long for big integer long long int p = 0, q = 0; for (long long int i = 2; (i * i * i) <= n; i++) { // If N does not divisible by i if (n % i != 0) continue; // if N/i divisible by i if ((n / i) % i == 0) { p = i; // Value of p q = n / (i * i); // Value of q } else { q = i; // Value of q p = (long long int)round(sqrt(n / i)); // Value of p taking round // figure of square root value } } cout << "P is " << p << "\n" << "Q is " << q << endl;}// Driver codeint main(){ long long int N = 2023; // Function call solvePQ(N); return 0;} |
Java
import java.math.BigDecimal;import java.math.RoundingMode;public class GFG { // Function to find P and Q public static void solvePQ(int n) { // Taking long long for big integer long p = 0, q = 0; for (long i = 2; (i * i * i) <= n; i++) { // If N does not divisible by i if (n % i != 0) continue; // if N/i divisible by i if ((n / i) % i == 0) { p = i; // Value of p q = n / (i * i); // Value of q } else { q = i; // Value of q p = (long)Math.round(Math.sqrt(n / i)); // Value of p taking round // figure of square root value } } System.out.println("P is " + p); System.out.println("Q is " + q); } // Driver code public static void main(String[] args) { int N = 2023; // Function call solvePQ(N); }}// This code is contributed by hkdass001. |
Python3
import mathdef solvePQ(n): p = 0 q = 0 for i in range(2, int(math.pow(n, 1 / 3)) + 1): if n % i != 0: continue if (n / i) % i == 0: p = i q = n / (i * i) else: q = i p = int(math.sqrt(n / i)) print(p, q)N = 2023solvePQ(N) |
C#
// C# program for above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // Function to find P and Q static void solvePQ(long n) { // Taking long long for big integer long p = 0, q = 0; for (long i = 2; (i * i * i) <= n; i++) { // If N does not divisible by i if (n % i != 0) continue; // if N/i divisible by i if ((n / i) % i == 0) { p = i; // Value of p q = n / (i * i); // Value of q } else { q = i; // Value of q p = (long)(Math.Sqrt(n / i)); // Value of p taking round // figure of square root value } } Console.Write("P is " + p + "\n" + "Q is " + q); } // Driver code static public void Main() { long N = 2023; // Function call solvePQ(N); }} |
Javascript
// JavaScript code for the above approachfunction solvePQ(n) {// Declare variables for P and Qlet p = 0;let q = 0;// Iterate from 2 to the cube root of nfor (let i = 2; i * i * i <= n; i++) {// If n is not divisible by i, continueif (n % i !== 0) {continue;}// If n/i is divisible by iif ((n / i) % i === 0) { p = i; q = n / (i * i);}// Otherwiseelse { q = i; p = Math.round(Math.sqrt(n / i));}}console.log("P is " + p);console.log("Q is " + q);}// Test with n = 2023solvePQ(2023);//This code is contributed by ik_9 |
Output
P is 17 Q is 7
Time Complexity: O(3?n)
Auxiliary space: O(1)
Method 2:
Approach:
- Define a function isPrime that takes an integer n and returns a boolean indicating whether n is prime or not.
- If n is less than 2, return false.
- For each integer i from 2 up to the square root of n, do:
- If n is divisible by i, return false.
- Return true.
- Define a function findPQ that takes an integer N and two integer references P and Q.
- Create an empty vector primes.
- For each integer i from 2 up to the square root of N, do:
- If i is prime (i.e., isPrime(i) returns true), add i to the primes vector.
- For each integer p in the primes vector, do:
- If N is divisible by p * p and (N / (p * p)) is prime, do:
- Set P = p and Q = N / (p * p).
- Return from the function.
- If N is divisible by p * p and (N / (p * p)) is prime, do:
- If no such P and Q are found, set P and Q to 0 (or any other value to indicate failure).
- Call the findPQ function with the input value of N and references to P and Q.
- Output the resulting values of P and Q.
Below is the implementation of the above approach:
C++
// CPP code of the above approach#include <iostream>#include <vector>using namespace std;bool isPrime(int n){ if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}void findPQ(int N, int& P, int& Q){ vector<int> primes; for (int i = 2; i * i <= N; i++) { if (isPrime(i)) primes.push_back(i); } for (int p : primes) { if (N % (p * p) == 0 && isPrime(N / (p * p))) { P = p; Q = N / (p * p); return; } }}int main(){ int N = 175; int P, Q; findPQ(N, P, Q); cout << "P = " << P << ", Q = " << Q << endl; return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java code of the above approachimport java.util.*;public class Main { static boolean isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } static void findPQ(int N, int[] pq) { ArrayList<Integer> primes = new ArrayList<>(); for (int i = 2; i * i <= N; i++) { if (isPrime(i)) primes.add(i); } for (int p : primes) { if (N % (p * p) == 0 && isPrime(N / (p * p))) { pq[0] = p; pq[1] = N / (p * p); return; } } } public static void main(String[] args) { int N = 175; int[] pq = new int[2]; findPQ(N, pq); System.out.println("P = " + pq[0] + ", Q = " + pq[1]); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python3 code of the above approachimport mathdef isPrime(n): if (n < 2): return False for i in range(2, int(math.sqrt(n))+1): if (n % i == 0): return False return Truedef findPQ(N): P, Q = None, None primes = [] for i in range(2, int(math.sqrt(N))+1): if (isPrime(i)): primes.append(i) for p in primes: if (N % (p * p) == 0 and isPrime(N // (p * p))): P = p Q = N // (p * p) break return P, QN = 175P, Q = findPQ(N)print(f"P = {P}, Q = {Q}") |
C#
//C# code of the above approachusing System;using System.Collections.Generic;public class MainClass { static bool IsPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } static void FindPQ(int N, int[] pq) { List<int> primes = new List<int>(); for (int i = 2; i * i <= N; i++) { if (IsPrime(i)) primes.Add(i); } foreach(int p in primes) { if (N % (p * p) == 0 && IsPrime(N / (p * p))) { pq[0] = p; pq[1] = N / (p * p); return; } } } public static void Main(string[] args) { int N = 175; int[] pq = new int[2]; FindPQ(N, pq); Console.WriteLine("P = " + pq[0] + ", Q = " + pq[1]); }} |
Javascript
// Javascript code of the above approachfunction isPrime(n) { if (n < 2) return false; for (let i = 2; i * i <= n; i++) { if (n % i === 0) return false; } return true;}function findPQ(N) { const primes = []; for (let i = 2; i * i <= N; i++) { if (isPrime(i)) primes.push(i); } for (const p of primes) { if (N % (p * p) === 0 && isPrime(N / (p * p))) { return [p, N / (p * p)]; } } return null;}const N = 175;const [P, Q] = findPQ(N);if (P !== undefined && Q !== undefined) { console.log(`P = ${P}, Q = ${Q}`);} else { console.log("No valid P and Q found.");}// This code is contributed by Prajwal Kandekar |
Output
P = 5, Q = 7
Time Complexity: O(n*logn)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
