Author : Ivan Ganatra
Ishita Jain
Tester: Ishita Jain, Ayushi Somani
Editorialist: Ivan Ganatra, Ishita Jain
DIFFICULTY : Medium
PREREQUISITES : Basic observation, Prime Numbers, Sieve of eratosthenes
PROBLEM:
Given a positive integers N. We can prove that every N can be divided by xi, where x and i both are positive integers and x>1. For each N, find out the value of x for which i will be maximum. If multiple solutions exist, then print the maximum value of x.
SOLUTION:
In the prime factorization of N, we have to find the maximum number x,either composite or prime, that can divide N maximum number of times.
N%xi==0, find x for which i is maximum, here x & i are integers and x>1.
Let’s say we went in search of x.
And we found the number x.
And we wrote its prime factorization.
So,
x=(p1)^{x1} *(p2)^{x2}*(p3)^{x3}…..(pn)^{xn}.
x^{i}=(p1)^{x1*i} *(p2)^{x2*i}*(p3)^{x3*i}…..(pn)^{xn*i}. (We then wrote x^i).
As you can see here, if xi divides N then (pi)xi*i will also divide N, so if x is a number having maximum i, then there should not be any number like (pi)^{xi*i} having power xi* i>i, hence xi should be 1,so that xi*i=i.
So our xi can only be of the form,
x^{i}=(p1)^{i} *(p2)^{i}*(p3)^{i}…..(pn)^{i}.
Hence, x=(p1*p2*p3*…..pn).
This simply means we want to find a product of prime numbers like p,which can divide N for maximum value of i.
So for this we use a concept, and implement using sieve.
With the help of sieve we will create a prime boolean array.
So, we first traverse through the loop,
At i=2,
Now we will visit all multiples of 2 and at each multiple for e.g. at 6, we count how many times 2 divides 6. If it divides more than previous maxi[6] (which is initially 0), then we will update to maxi[6]=1 and X[6]=2.
At i=3,
when we visit 6, since 3 divides 6 only 1 time, and previous maxi[6]=1, hence we will update to X[6]=X[6]*3=6 and keep maxi[6] as it is.
Similarly we will traverse all the multiples of prime numbers and update the values of maxi and x.
Code
if(count>maxi[j])
{
maxi[j]=count;
x[j]=i;
}
else if(count==maxi[j])
{
maxi[j]=count;
x[j]*=i;
}
| Numbers | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| Prime boolean | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| Maximum i | 1 | 1 | 2 | 1 | 1 | 1 | 3 | 2 |
| X | 2 | 3 | 2 | 5 | 6 | 7 | 2 | 3 |
Now, whenever we are asked for x for which i will be maximum, we will just return X[N] as our answer in constant time complexity.
TIME COMPLEXITY
Time complexity is \mathcal O(n log (log n)) for Sieve of Eratosthenes and since in the second loop of sieve, we are also using a while loop, it will add log(n) time complexity, hence final TC will be \mathcal O(nlogn)*log (log n)).
Setter's Solution:
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MAX 1000010
vector<bool>prime(MAX,true);
vector<int>maxi(MAX);
vector<int>x(MAX);
void sieve(){
prime[0]=0;
prime[1]=0;
maxi[1]=1;
x[1]=1;
for(int i=2;i<MAX;i++)
{
if(prime[i]==1)
{
maxi[i]=1;
x[i]=i;
for(int j=i+i;j<MAX;j+=i)
{
prime[j]=0;
int y=j;
int count=0;
while(y!=1 && y%i==0)
{
count++;
y/=i;
}
if(count>maxi[j])
{
maxi[j]=count;
x[j]=i;
}
else if(count==maxi[j])
{
maxi[j]=count;
x[j]*=i;
}
}
}
}
}
int main()
{
fast;
sieve();
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<x[n]<<endl;
}
return 0;
}
Tester's Solution:
import java.util.*;
import java.io.*;
public class Main
{
static int S = 1000000;
static int prime[] = new int[S+5];
static void sieveMaker() {
for(int i = 2; i <= S; i++)
prime[i] = i;
for(int i = 2; i*i <= S; i++) {
if(prime[i] == i) {
for(int j = i*i; j <= S; j += i) prime[j] = i;
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
sieveMaker();
int t = Integer.parseInt(sc.readLine());
List<Integer> ans = new ArrayList<>();
while(t-->0){
int n = Integer.parseInt(sc.readLine());
int res = 1, p = 0;
while(n > 1) {
int k = prime[n], freq = 0;
while(n % k == 0) {
n /= k;
freq += 1;
}
if(freq > p){
res = k;
p = freq;
}
else if(freq == p) res *= k;
}
ans.add(res);
}
for(int x:ans)
System.out.println(x);
}
}
Doubts and alternative solutions are welcome.
.