|
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++
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;
int gpf[maxn];
void modifiedSieve()
{
memset(gpf, 0, sizeof(gpf));
gpf[0] = 0;
gpf[1] = 1;
for (int i = 2; i < maxn; i++) {
if (gpf[i] > 0)
continue;
for (int j = i; j < maxn; j += i) {
gpf[j] = max(i, gpf[j]);
}
}
}
int greatestValidInt(int N)
{
modifiedSieve();
for (int i = N; i > 0; i--) {
if (gpf[i] > sqrt(i)) {
return i;
}
}
return -1;
}
int main()
{
int N = 25;
cout << greatestValidInt(N);
return 0;
}
|
Java
public class GFG {
final static int maxn = 100001;
static int gpf[] = new int[maxn];
static void modifiedSieve()
{
for (int i = 0; i < maxn; i++ )
gpf[i] = 0;
gpf[0] = 0;
gpf[1] = 1;
for (int i = 2; i < maxn; i++) {
if (gpf[i] > 0)
continue;
for (int j = i; j < maxn; j += i) {
gpf[j] = Math.max(i, gpf[j]);
}
}
}
static int greatestValidInt(int N)
{
modifiedSieve();
for (int i = N; i > 0; i--) {
if (gpf[i] > Math.sqrt(i)) {
return i;
}
}
return -1;
}
public static void main (String[] args)
{
int N = 25;
System.out.println(greatestValidInt(N));
}
}
|
Python3
import math
maxn = 100001
gpf = [0 for _ in range(maxn)]
def modifiedSieve():
gpf[0] = 0
gpf[1] = 1
for i in range(2, maxn):
if (gpf[i] > 0):
continue
for j in range(i, maxn, i):
gpf[j] = max(i, gpf[j])
def greatestValidInt(N):
modifiedSieve()
for i in range(N, 0, -1):
if (gpf[i] > math.sqrt(i)):
return i
return -1
if __name__ == "__main__":
N = 25
print(greatestValidInt(N))
|
C#
using System;
public class GFG {
static int maxn = 100001;
static int[] gpf = new int[maxn];
static void modifiedSieve()
{
for (int i = 0; i < maxn; i++)
gpf[i] = 0;
gpf[0] = 0;
gpf[1] = 1;
for (int i = 2; i < maxn; i++) {
if (gpf[i] > 0)
continue;
for (int j = i; j < maxn; j += i) {
gpf[j] = Math.Max(i, gpf[j]);
}
}
}
static int greatestValidInt(int N)
{
modifiedSieve();
for (int i = N; i > 0; i--) {
if (gpf[i] > Math.Sqrt(i)) {
return i;
}
}
return -1;
}
public static void Main(string[] args)
{
int N = 25;
Console.WriteLine(greatestValidInt(N));
}
}
|
Javascript
<script>
const maxn = 100001;
let gpf = new Array(maxn);
function modifiedSieve()
{
gpf.fill(0);
gpf[0] = 0;
gpf[1] = 1;
for (let i = 2; i < maxn; i++)
{
if (gpf[i] > 0) continue;
for (let j = i; j < maxn; j += i) {
gpf[j] = Math.max(i, gpf[j]);
}
}
}
function greatestValidInt(N) {
modifiedSieve();
for (let i = N; i > 0; i--)
{
if (gpf[i] > Math.sqrt(i))
{
return i;
}
}
return -1;
}
let N = 25;
document.write(greatestValidInt(N));
</script>
|
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
|
