Given a positive integer N, the task is to find the largest number in the range [1, N] such that the square root of the number is less than its greatest prime factor.
Input: N = 15
Output: 15
Explanation: The prime factors of 15 are {3, 5}. The square root of 15 is 3.87 (i.e, 3.87 < 5). Therefore 15 is the largest valid integer in the given range.Input: N = 25
Output: 23
Approach: The given problem can be solved by using the Sieve of Eratosthenes with a few modifications. Create an array gpf[], which stores the Greatest Prime Factor of all integers in the given range. Initially, gpf[] = {0}. Using Sieve, initialize all the indices of the array gpf[] with the greatest prime factor of the respective index similar to the algorithm discussed in this article.
Now, iterate over the range [N, 1] in a reverse manner and print the first integer whose square root of the number is less than its greatest prime factor.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int maxn = 100001;// Stores the Greatest Prime Factorint gpf[maxn];// Modified Sieve to find the Greatest// Prime Factor of all integers in the// range [1, maxn]void modifiedSieve(){ // Initialize the array with 0 memset(gpf, 0, sizeof(gpf)); gpf[0] = 0; gpf[1] = 1; // Iterate through all values of i for (int i = 2; i < maxn; i++) { // If i is not a prime number if (gpf[i] > 0) continue; // Update the multiples of i for (int j = i; j < maxn; j += i) { gpf[j] = max(i, gpf[j]); } }}// Function to find integer in the range// [1, N] such that its Greatest Prime// factor is greater than its square rootint greatestValidInt(int N){ modifiedSieve(); // Iterate through all values of // i in the range [N, 1] for (int i = N; i > 0; i--) { // If greatest prime factor of i // is greater than its square root if (gpf[i] > sqrt(i)) { // Return answer return i; } } // If no valid integer exist return -1;}// Driver Codeint main(){ int N = 25; cout << greatestValidInt(N); return 0;} |
Java
// Java program for the above approachpublic class GFG { final static int maxn = 100001; // Stores the Greatest Prime Factor static int gpf[] = new int[maxn]; // Modified Sieve to find the Greatest // Prime Factor of all integers in the // range [1, maxn] static void modifiedSieve() { // Initialize the array with 0 for (int i = 0; i < maxn; i++ ) gpf[i] = 0; gpf[0] = 0; gpf[1] = 1; // Iterate through all values of i for (int i = 2; i < maxn; i++) { // If i is not a prime number if (gpf[i] > 0) continue; // Update the multiples of i for (int j = i; j < maxn; j += i) { gpf[j] = Math.max(i, gpf[j]); } } } // Function to find integer in the range // [1, N] such that its Greatest Prime // factor is greater than its square root static int greatestValidInt(int N) { modifiedSieve(); // Iterate through all values of // i in the range [N, 1] for (int i = N; i > 0; i--) { // If greatest prime factor of i // is greater than its square root if (gpf[i] > Math.sqrt(i)) { // Return answer return i; } } // If no valid integer exist return -1; } // Driver Code public static void main (String[] args) { int N = 25; System.out.println(greatestValidInt(N)); } }// This code is contributed by AnkThon |
Python3
# python program for the above approachimport mathmaxn = 100001# Stores the Greatest Prime Factorgpf = [0 for _ in range(maxn)]# Modified Sieve to find the Greatest# Prime Factor of all integers in the# range [1, maxn]def modifiedSieve(): # Initialize the array with 0 gpf[0] = 0 gpf[1] = 1 # Iterate through all values of i for i in range(2, maxn): # If i is not a prime number if (gpf[i] > 0): continue # Update the multiples of i for j in range(i, maxn, i): gpf[j] = max(i, gpf[j])# Function to find integer in the range# [1, N] such that its Greatest Prime# factor is greater than its square rootdef greatestValidInt(N): modifiedSieve() # Iterate through all values of # i in the range [N, 1] for i in range(N, 0, -1): # If greatest prime factor of i # is greater than its square root if (gpf[i] > math.sqrt(i)): # Return answer return i # If no valid integer exist return -1# Driver Codeif __name__ == "__main__": N = 25 print(greatestValidInt(N))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { static int maxn = 100001; // Stores the Greatest Prime Factor static int[] gpf = new int[maxn]; // Modified Sieve to find the Greatest // Prime Factor of all integers in the // range [1, maxn] static void modifiedSieve() { // Initialize the array with 0 for (int i = 0; i < maxn; i++) gpf[i] = 0; gpf[0] = 0; gpf[1] = 1; // Iterate through all values of i for (int i = 2; i < maxn; i++) { // If i is not a prime number if (gpf[i] > 0) continue; // Update the multiples of i for (int j = i; j < maxn; j += i) { gpf[j] = Math.Max(i, gpf[j]); } } } // Function to find integer in the range // [1, N] such that its Greatest Prime // factor is greater than its square root static int greatestValidInt(int N) { modifiedSieve(); // Iterate through all values of // i in the range [N, 1] for (int i = N; i > 0; i--) { // If greatest prime factor of i // is greater than its square root if (gpf[i] > Math.Sqrt(i)) { // Return answer return i; } } // If no valid integer exist return -1; } // Driver Code public static void Main(string[] args) { int N = 25; Console.WriteLine(greatestValidInt(N)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approachconst maxn = 100001;// Stores the Greatest Prime Factorlet gpf = new Array(maxn);// Modified Sieve to find the Greatest// Prime Factor of all integers in the// range [1, maxn]function modifiedSieve(){ // Initialize the array with 0 gpf.fill(0); gpf[0] = 0; gpf[1] = 1; // Iterate through all values of i for (let i = 2; i < maxn; i++) { // If i is not a prime number if (gpf[i] > 0) continue; // Update the multiples of i for (let j = i; j < maxn; j += i) { gpf[j] = Math.max(i, gpf[j]); } }}// Function to find integer in the range// [1, N] such that its Greatest Prime// factor is greater than its square rootfunction greatestValidInt(N) { modifiedSieve(); // Iterate through all values of // i in the range [N, 1] for (let i = N; i > 0; i--) { // If greatest prime factor of i // is greater than its square root if (gpf[i] > Math.sqrt(i)) { // Return answer return i; } } // If no valid integer exist return -1;}// Driver Codelet N = 25;document.write(greatestValidInt(N));// This code is contributed by gfgking.</script> |
Output:
23
Time Complexity: O(N*log N)
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!
