Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Maximum Factors Problem CodeChef Solution
Problem -Maximum Factors Problem CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Maximum Factors Problem CodeChef Solution in C++17
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std::chrono;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
template<class T>
using min_heap = priority_queue<T, vector<T>, greater<T> >;
//--------------------------------IO(Debugging)-----------------------------//
template<class T> istream& operator >> (istream &is, vector<T>& V) {
for (auto &e : V)
is >> e;
return is;
}
template<class T, size_t N> istream& operator >> (istream &is, array<T, N>& V) {
for (auto &e : V)
is >> e;
return is;
}
template<class T1, class T2> istream& operator >> (istream &is, pair<T1, T2>& V) {
is >> V.first >> V.second;
return is;
}
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
static char buffer[64];
int index = 0;
__uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
if (value < 0)
os << '-';
else if (T == 0)
return os << '0';
for (; T > 0; ++index) {
buffer[index] = static_cast<char>('0' + (T % 10));
T /= 10;
}
while (index > 0)
os << buffer[--index];
return os;
}
istream& operator >> (istream& is, __int128& T) {
static char buffer[64];
is >> buffer;
size_t len = strlen(buffer), index = 0;
T = 0; int mul = 1;
if (buffer[index] == '-')
++index, mul *= -1;
for (; index < len; ++index)
T = T * 10 + static_cast<int>(buffer[index] - '0');
T *= mul;
return is;
}
#endif
template<typename CharT, typename Traits, typename T>
ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, T const &val) {
return (out << val << " ");
}
template<typename CharT, typename Traits, typename T1, typename T2>
ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, pair<T1, T2> const &val) {
return (out << "(" << val.first << "," << val.second << ") ");
}
template<typename CharT, typename Traits, template<typename, typename...> class TT, typename... Args>
ostream& operator << (std::basic_ostream<CharT, Traits> &out, TT<Args...> const &cont) {
out << "[ ";
for (auto && elem : cont) _containerprint(out, elem);
return (out << "]");
}
template<class L, class R> ostream& operator << (ostream& out, pair<L, R> const &val) {
return (out << "(" << val.first << "," << val.second << ") ");
}
template<typename L, size_t N> ostream& operator << (ostream& out, array<L, N> const &cont) {
out << "[ ";
for (auto && elem : cont) _containerprint(out, elem);
return (out << "]");
}
template<class T> ostream& operator<<(ostream &out, ordered_set<T> const& S) {
out << "{ ";
for (const auto& s : S) out << s << " ";
return (out << "}");
}
template<class L, class R, class chash = std::hash<L> > ostream & operator << (ostream &out, gp_hash_table<L, R, chash> const& M) {
out << "{ ";
for (const auto& m : M) out << "(" << m.first << ":" << m.second << ") ";
return (out << "}");
}
template<class P, class Q = vector<P>, class R = less<P> > ostream & operator << (ostream& out, priority_queue<P, Q, R> const& M) {
static priority_queue<P, Q, R> U;
U = M;
out << "{ ";
while (!U.empty())
out << U.top() << " ", U.pop();
return (out << "}");
}
template<class P> ostream& operator << (ostream& out, queue<P> const& M) {
static queue<P> U;
U = M;
out << "{ ";
while (!U.empty())
out << U.front() << " ", U.pop();
return (out << "}");
}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " : " << arg1 << " | ";
__f(comma + 1, args...);
}
#else
#define trace(...) 1
#endif
//------------------------------------RNG-----------------------------------//
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int64_t random_long(long long l = LLONG_MIN, long long r = LLONG_MAX) {
uniform_int_distribution<int64_t> generator(l, r);
return generator(rng);
}
struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
template<typename L, typename R>
size_t operator()(pair<L, R> const& Y) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);
}
};
//------------------------------------Defines-------------------------------//
#define ll long long
//#define ull unsigned long long
#define ld long double
#define getline_clear cin.ignore()
#define merge_arrays(a,b,c) merge(all(a),all(b),back_inserter(c))
#define uid(a, b) uniform_int_distribution<int>(a, b)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
typedef long long LL;
typedef pair<ll, ll> pii;
typedef pair<LL, LL> pll;
typedef pair<string, string> pss;
typedef vector<long long int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
#define elif else if
#define rep(i, n) for(int i=0;i<n;i++)
#define repn(i, n) for(int i=1;i<=n;i++)
#define reset(a, b) memset(a, b, sizeof(a))
#define cy cout<<"YES"<<"\n"
#define cn cout<<"NO"<<'\n'
#define cyo cout <<"YO"<<'\n';
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz size()
#define mem1(a) memset(a,-1,sizeof(a))
//---------------------Global Constants and Functions-----------------------//
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
//ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} //only for prime m
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
//-----------------------------Code begins----------------------------------//
const int INF = 1000000000;
typedef tree<pii, null_type, greater<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds1;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds2;
const int maxn = 2505;
map<pair<ll,ll>, ll>m;
string s;
int solve(int l ,int r , char a){
int mid = (l + r)/2;
int cnt1 = 0, cnt2 = 0;
if(r == l){
return (s[l] == a ? 0 : 1);
}
for(int i = l;i<=mid;i++)cnt1+=(s[i] == a ? 1:0);
for(int i = mid + 1;i<=r;i++)cnt2+=(s[i] == a ? 1:0);
m[{l,mid}] = cnt1;
m[{mid+1,r}] = cnt2;
return min(m[{l,mid}] + solve(mid+1,r,a+1), m[{mid + 1, r}] + solve(l,mid,a+1));
}
void solve() {
ll n;
cin >> n;
map<ll,ll> mp;
for(int i = 2 ; i*i <= n ;i++){
while(n%i == 0){
mp[i]++;
n/=i;
}
}
if(n > 1)mp[n]++;
ll ans = 0;
//trace(mp);
ll tot = 1;
for(auto i:mp){
tot *= (i.se +1);
}
ll mx = -1;
for(auto i:mp){
tot/=(i.se + 1);
tot*=i.se;
if(tot > mx){
mx = tot;
ans = i.fi;
}
tot/= i.se;
tot*=(i.se +1);
}
cout << ans << '\n';
}
int32_t main( void ) {
ios_base::sync_with_stdio(false),
cin.tie(NULL);
// freopen("convention.in","r",stdin);
// freopen("convention.out","w",stdout);
int T = 1;
cin >> T;
for (int t = 1; t <= T; t++) {
//cout << "Case #" << t << ": ";
solve();
}
return 0;
/*cout << "Time taken by function: "
<< duration.count() << " microseconds" << endl;*/
} Maximum Factors Problem CodeChef Solution in C++14
#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds; //for policy based ds
using namespace std;
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
for (int &i : arr) \
cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
time_t Begin;
//////////////////Debug///////////////
#define debug(x) \
cout << #x << " "; \
_print(x); \
cout << endl;
void _print(ll t)
{
cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
for (ll i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
cout << "{";
_print(p.ff);
cout << ",";
_print(p.ss);
cout << "}";
}
template <class T>
void _print(vector<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(set<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
cout << "[ ";
for (auto i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
void init()
{
Begin = clock();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}
vector<int> computeLps(string s, int M)
{
int len = 0;
vector<int> lps(M + 20);
lps[0] = 0;
int i = 1;
while (i < M)
{
if (s[i] == s[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
// debug(len);
return lps;
}
int ceiling(int x, int y)
{
int res = x / y;
if (x % y)
{
if (x >= 0)
res++;
}
return res;
}
vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> prefix(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
}
}
return prefix;
}
int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
// cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}
int toInt(string &s)
{
int res = 0;
for (char c : s)
res = res * 10 + (c - '0');
return res;
}
bool isValid(int i, int j, int n, int m)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};
int numberOfDivisors(int x)
{
int res = 1;
int k = 1, mxK = 0, num = x;
for (int i = 2; i * i <= x; i++)
{
int cnt = 0;
while (x % i == 0)
{
x /= i;
cnt++;
}
res *= cnt + 1;
if (cnt > mxK)
{
mxK = cnt;
k = i;
}
}
if (x > 1)
{
if (mxK < 1)
{
k = x;
}
res *= 2;
}
return k;
}
int32_t main()
{
init();
//--------------------
int t = 1;
cin >> t;
// int aMax = 1e7 + 10;
// vector<int> fac = calcFactorial(aMax), facInverse = factorialInverseUnderMod(aMax);
for (int tt = 1; tt <= t; tt++)
{
int n;
cin >> n;
// debug(v);
cout << numberOfDivisors(n) << "\n";
}
//---------------------------
timeTaken();
return 0;
}Maximum Factors Problem CodeChef Solution in PYTH 3
# the answer is the prime factor of n that has the highest exponent, small is tiebreak
import math
pf = []
def pfe(x,l):
for i in range(l,math.floor(math.sqrt(x))+2):
if x % i == 0:
pf.append(i)
pfe(x//i,i)
return
if x > 1: pf.append(x)
for tea in[0]*int(input()):
n = int(input())
pf = []
pfe(n,2)
lol = dict()
for i in pf:
if i in lol:
lol[i] += 1
else:
lol[i] = 1
maxx = -1
deMax = -1
for i in sorted(list(lol)):
if lol[i] > maxx:
maxx = lol[i]
deMax = i
print(deMax)Maximum Factors Problem CodeChef Solution in C
#include <stdio.h>
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
int k=0;
int maxp=0;
for(register int i=2; (i*i)<=n; i++)
{
int c=0;
if(n%i==0)
{
int p=0;
while(n%i==0)
{
n=n/i;
p++;
}
if(p>maxp)
{
maxp=p;
k=i;
}
}
}
if(maxp==0)
k=n;
printf("%d \n", k);
}
}Maximum Factors Problem CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Reader sc=new Reader();
int t=sc.nextInt();
while(t>0){
t--;
int n=sc.nextInt();
solve(n);
}
}
public static void solve(int n)
{
int res=n,maxPow=Integer.MIN_VALUE;
for(int i=2;(i*i)<=n;i++)
{
if(n%i==0)
{
int pow=0;
while(n%i==0)
{
n/=i;
pow++;
}
if(maxPow<pow)
{
maxPow=pow;
res=i;
}
}
}
System.out.println(res);
}
}
Maximum Factors Problem CodeChef Solution in PYPY 3
import os
import sys
from io import BytesIO, IOBase
from collections import Counter
nmbr = lambda: int(input())
lst = lambda: list(map(int, input().split()))
def main():
def fn(x):
PI=float('inf')
mp = Counter()
while x&1==0:
x>>=1
mp[2]+=1
p=3
while p*p<=n:
while x%p==0:
mp[p]+=1
x//=p
p+=2
if x>2:
mp[x]+=1
mn=0
ans=x
# print(mp)
for key in mp:
if mp[key]>mn or (mp[key]==mn and key<ans):
mn=mp[key]
ans=key
return ans
for _ in range(nmbr()):
n = nmbr()
ans=fn(n)
sys.stdout.write(str(ans) + '\n')
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
for t in range(1): main() # int(input())):Maximum Factors Problem CodeChef Solution in PYTH
#!/usr/bin/env python
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
from __builtin__ import xrange as range
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import permutations
from collections import defaultdict
def chk(a):
n=len(a)
ans=0
for i in range(n):
if(i-1>=0 and i+1<n and a[i-1]<a[i]>a[i+1]):
ans+=1
elif(i-1>=0 and i+1<n and a[i-1]>a[i]<a[i+1]):
ans+=1
return ans
def sieve():
l=[True]*(10**5)
ans=[]
for i in range(2,10**5):
if(l[i]):
for j in range(i*2,10**5,i):
l[j]=False
ans.append(i)
return ans
def main():
s=sieve()
s1=set(s)
for _ in range(int(input())):
n=int(input())
d=dict()
for i in s:
if(n%i==0):
t=0
while(n%i==0):
n//=i
t+=1
d[i]=t
if(n!=1):
d[n]=1
print(max(d.keys(),key=lambda x:(d[x],-x)))
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
"""Prints the values to a stream, or to sys.stdout by default."""
sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
at_start = True
for x in args:
if not at_start:
file.write(sep)
file.write(str(x))
at_start = False
file.write(kwargs.pop("end", "\n"))
if kwargs.pop("flush", False):
file.flush()
if sys.version_info[0] < 3:
sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion
if __name__ == "__main__":
main()Maximum Factors Problem CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
namespace Codeforces
{
public class Program
{
private static int _mod = (int)1e9 + 7;
private static int[][] _prec;
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine());
for (int i = 0; i < t; i++)
Solve();
}
public static void Solve()
{
int n = GetInt();
int ans = PrimeFactors(n)
.GroupBy(_ => _)
.OrderByDescending(grp => grp.Count())
.ThenBy(grp => grp.Key)
.First()
.Key;
#if DEBUG
Console.Write("Answer is -----------> ");
#endif
Console.WriteLine(ans);
}
public static int NoverKwithMod(int n, int k)
{
int ans;
long x = ModFacDownTo(n, n - k + 1);
long y = KInverse(ModFac(k));
ans = (int)((x * y) % _mod);
return ans;
}
// k! % m
public static int ModFac(int k)
{
long r = 1;
for (int i = 1; i <= k; i++)
{
r = (r * i) % _mod;
}
return (int)r;
}
// (n * (n-1) * ... * k ) % m
public static int ModFacDownTo(int n, int k)
{
long r = 1;
for (int i = n; i >= k; i--)
{
r = (r * i) % _mod;
}
return (int)r;
}
public static int KInverse(int k)
{
return ModPow(k, _mod - 2);
}
public static int ModPow(int a, int b)
{
if (a >= _mod)
throw new ArgumentException();
if (b == 0)
return 1;
if (b == 1)
return a;
int factor = b % 2 == 0 ? 1 : a;
a = (int)(((long)a * a) % _mod);
b /= 2;
return (int)(((long)factor * ModPow(a, b)) % _mod);
}
public static bool IsPrime(int n)
{
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
public static List<int> PrimeFactors(int n)
{
var factors = new List<int>();
while (n % 2 == 0)
{
factors.Add(2);
n /= 2;
}
int p = 3;
while (n >= 2)
{
if (n % p == 0)
{
factors.Add(p);
n /= p;
continue;
}
p += 2;
if (p * p > n)
{
factors.Add(n);
break;
}
}
return factors;
}
public static int GetInt() => int.Parse(Console.ReadLine());
public static long GetLong() => long.Parse(Console.ReadLine());
public static int[] GetIntArray() => Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
public static long[] GetLongArray() => Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
public static double[] GetDoublesArray() => Console.ReadLine().Trim().Split(' ').Select(d => Convert.ToDouble(d, CultureInfo.InvariantCulture)).ToArray();
public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
public static long Gcd(long[] a) => a.Aggregate(a[0], (x, y) => Gcd(x, y));
public static long Lcm(long a, long b) => a * b / Gcd(a, b);
public static long Lcm(IEnumerable<int> a) => a.Aggregate(1L, (x, y) => Lcm(x, y));
public static void Swap(ref long a, ref long b)
{
long t = a;
a = b;
b = t;
}
public static void Swap(ref int a, ref int b)
{
int t = a;
a = b;
b = t;
}
public static void OutputSequence(IEnumerable<long> x) => Console.WriteLine($" >> " + string.Join(", ", x));
public static string Rev(string s) => string.Concat(s.ToArray().Reverse());
public static Dictionary<long, long> Frequencies(long[] a)
{
var ans = new Dictionary<long, long>();
foreach (int k in a)
{
if (ans.ContainsKey(k))
ans[k]++;
else
ans[k] = 1;
}
return ans;
}
}
}Maximum Factors Problem CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
n := readNum(reader)
res := solve(n)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
fmt.Println(buf.String())
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
const X = 100000
var PM []int
func init() {
set := make([]bool, X)
for i := 2; i < X; i++ {
if !set[i] {
PM = append(PM, i)
for j := i; j < X; j += i {
set[j] = true
}
}
}
}
func solve(n int) int {
var cnt []Pair
for i := 0; i < len(PM) && n > 1; i++ {
if n%PM[i] == 0 {
var tmp int
for n%PM[i] == 0 {
tmp++
n /= PM[i]
}
cnt = append(cnt, Pair{PM[i], tmp})
}
}
cnt = append(cnt, Pair{n, 1})
var ans int
for i := 1; i < len(cnt); i++ {
if cnt[i].second > cnt[ans].second {
ans = i
}
}
return cnt[ans].first
}
type Pair struct {
first, second int
}Maximum Factors Problem CodeChef Solution Review:
In our experience, we suggest you solve this Maximum Factors Problem CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum Factors Problem CodeChef Solution.
Conclusion:
I hope this Maximum Factors Problem CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
