# Divide Till You Can(CC025) - Editorial

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 (which is initially 0), then we will update to maxi=1 and X=2.

At i=3,

when we visit 6, since 3 divides 6 only 1 time, and previous maxi=1, hence we will update to X=X*3=6 and keep maxi 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;
prime=0;
maxi=1;
x=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{
sieveMaker();
List<Integer> ans = new ArrayList<>();
while(t-->0){

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;
}
}
for(int x:ans)
System.out.println(x);
}
}


Doubts and alternative solutions are welcome.

1 Like

Something is wrong with the judge .
I submitted my solution in C, it is giving WA. I copied the CPP code from the editorial and submitted it, it gave AC.
So I thought of debugging my code using the editorialist’s code. I generated a big file of test cases consisting of all integers between 2 and 10^6 inclusive. I executed both the codes against these custom generated test cases. Both of them are giving exactly the same output. I don’t understand what’s wrong.

C Code
/*
Author: Chitturi Sai Suman
Created: 2021-04-13 10:13:07
*/
#include <stdio.h>
#define size 1000003
int spf[size] = {1};
void precompute() {
spf = spf = 1;
for(int i = 2; i < size; i += 2)
spf[i] = 2;
for(int i = 3; i < size; i += 2)
spf[i] = i;
for(int i = 3; i * i < size; i += 2)
if(spf[i] == i)
for(int j = i * i; j < size; j += i)
if(spf[j] == j)
spf[j] = i;
}
int solve(int n) {
int x = 0;
int c = 0;
while(n > 1) {
int s = spf[n];
int p = 0;
while(n > 1 && spf[n] == s) {
n /= s;
p++;
}
// fprintf(stderr, "p = %d\n", p);
if(p > c) {
x = s;
c = p;
}
else if(p == c) {
x *= s;
}
// fprintf(stderr, "x = %d\n", x);
}
return x;
}
int main() {
int t;
scanf("%d",&t);
precompute();
for(; t > 0; t--) {
int n;
scanf("%d", &n);
printf("%d\n", solve(n));
}
return 0;
}

CPP Code
#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<int> prime(MAX,true);
vector<int> maxi(MAX);
vector<int> x(MAX);
void sieve()
{
prime=0;
prime=0;
maxi=1;
x=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;
} Python program to generate test cases
"""
Author: Chitturi Sai Suman
Created: 2021-04-13 10:13:07
"""
from random import randint

def generate_input_as_string():
pass

def main():
test = 1000000 - 1
with open("in.in","w") as file:
file.write(str(test)+'\n')
for t in range(test):
string = str(t + 2)
file.write(string+"\n")

main()


@ivan123 test cases don’t follow constraints. The following code is giving RTE. In future, please make sure test cases follow the constraints.

RTE Code
/*
Author: Chitturi Sai Suman
Created: 2021-04-13 10:13:07
*/
#include <stdio.h>
#include <assert.h>
#define size 1000003
int spf[size] = {1};
void precompute() {
spf = spf = 1;
for(int i = 2; i < size; i += 2)
spf[i] = 2;
for(int i = 3; i < size; i += 2)
spf[i] = i;
for(int i = 3; i * i < size; i += 2)
if(spf[i] == i)
for(int j = i * i; j < size; j += i)
if(spf[j] == j)
spf[j] = i;
}
int solve(int n) {
int x = 0;
int c = 0;
while(n > 1) {
int s = spf[n];
int p = 0;
while(n > 1 && spf[n] == s) {
n /= s;
p++;
}
// fprintf(stderr, "p = %d\n", p);
if(p > c) {
x = s;
c = p;
}
else if(p == c) {
x *= s;
}
// fprintf(stderr, "x = %d\n", x);
}
return x;
}
int main() {
int t;
scanf("%d",&t);
precompute();
for(; t > 0; t--) {
int n;
scanf("%d", &n);
assert(n > 1 && n < 1000001);
printf("%d\n", solve(n));
}
return 0;
}