Contest Name:
CODICTION 2020
PROBLEM LINK:
Setter- Saniya
Tester- Pranay Garg
Editorialist- Pranay Garg
DIFFICULTY:
Easy
PRE-REQUISITES:
Sieve of Eratosthenes, Frequency array
PROBLEM:
Given an array A consisting of N elements, find the largest prime factor of each element and print the factor which occurs the most number of times.
QUICK-EXPLANATION:
Find the value of largest prime factor p_{i} for each element in the array A_{i} using Sieve and store their frequency using hashing. At last just print the factor which has maximum count.
EXPLANATION:
First of all, if you are new to Sieve, or if the quick explanation felt completely alien to you, visit the Sieve of Eratosthenes blog linked at GeeksforGeeks. This problem is pretty standard application of Sieve technique with slight variation, so make sure to read and drill the pre-requisites in your head 
.
Firstly, let’s try to solve the easier part of the problem -
Given an array A we need to find the count of each element of the array. Now since A[i]<=10^5 we can create an array count[100005] and initialize it with zero where count[i] represents the frequency of number i in the given array. Now we can simply iterate over all the elements of the array and increase the count of each element A[i].
Code
int count[100005]={0};
for(int i=0;i<n;i++) //n is the size of the array O(n) time comlexity
{
count[A[i]]++; //increasing the count of A[i]
}
Now coming to the harder part i.e efficiently finding the largest prime factor of each element -
We will use Sieve for this part, generally we use sieve to check whether a number is prime or not but here we will slightly modify it to find the smallest prime factor of each element.
For every prime number p we will calculate the smallest prime factor of all its multiples upto 10^5.
Look at the function below for more clarity.
Sieve variation
int prime[100005];
void SieveOfEratosthenes(int n)//O(nloglogn)
{
memset(prime, 0, sizeof(prime)); //initializing with default values
//prime[p] denotes the smallest prime factor of p if prime[p]>0 else p is a prime
number
for (int p=2; p*p<=n; p++)
{
if (prime[p] == 0) // p is a prime number
{
for (int i=p*p; i<=n; i += p) // iterate over all the multiples of p
{
if(prime[i]==0) // we are seeing this number for the first time
prime[i]=p;
else //we need the smallest prime factor
prime[i] = min(prime[i],p);
}
}
}
}
Combine both the part to get the deserved AC…
Suppose we have a number num and let its smallest prime factor be p, then we can find the largest prime factor by repeatedly dividing the number by p until it becomes a prime number (prime[num]=0) which will be the answer for that number.
Let num=180 then p=2 (prime[180]=2)
180/2 = 90 //prime[90]=2
90/2 = 45 //prime[45]=3
45/3 = 15 //prime[15]=3
15/3 = 5 //prime[5]=0
So, the largest prime factor of 180 will be 5.
For more clarity look at the code below
Code
while(prime[num]!=0)
{
num = num/prime[num];
}
//ans will be num
Now we just need to combine together all the parts. Kindly look at the solution part for that.
SOLUTION
Editorialist's solution
#include <bits/stdc++.h>
#define ll long long int
#define ironman ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
ll prime[100005];
void SieveOfEratosthenes(ll n)//O(nloglogn)
{
memset(prime, 0, sizeof(prime));
for (ll p=2; p*p<=n; p++)
{
if (prime[p] == 0)
{
for (ll i=p*p; i<=n; i += p)
{
if(prime[i]==0)
prime[i]=p;
else
prime[i] = min(prime[i],p);
}
}
}
}
int main()
{
ironman
ll t;
cin >> t;
assert(t>=1 && t<=10);
SieveOfEratosthenes(100000);
while(t--)
{
ll n;
cin >> n;
assert(n>=1 && n<=100000);
std::vector<ll> arr(n);
for(auto &i:arr)
{
cin >> i;
assert(i>=2 && i<=100000);
}
ll count[100005]={0};
for(auto i:arr)
{
ll a=i;
while(prime[a]!=0)
{
a = a/prime[a];
}
count[a]++;
}
ll ans = 0,fincount=0;
for(ll i=0;i<=100000;i++)
{
if(count[i]>fincount)
{
fincount = max(fincount,count[i]);
ans = i;
}
else if(count[i]==fincount)
ans = max(ans,i);
}
cout << ans << endl;
}
}
Time Complexity=O(NloglogN + 17*T*N)
Space Complexity=O(3*N)
Note:
There might be other ways of solving the problem, if you find one feel free to mention them in comment below. Also this is my first editorial so feel free to give any suggestion or ask any doubt related to the question.