import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc= new Scanner(System.in);
int t= sc.nextInt();
while(t–>0){
int n= sc.nextInt(); int k= sc.nextInt();
long res=1;long c=0;
for(int i=2;i<=n;i++){
res=res*i;
while(res%k==0){
res=res/k;
c++;
}}
System.out.println(c);
}
}}
I know why my approach is wrong tell me some other way
actually what we need to do is-;
prime factorise k and check for all its prime factors whose minimmum power that can divide n!.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
this is my code your approach i have implemented still tle whats wrong
your implementation is partially wrong…
i have made a well commented solution for you to understand, please see
not found and now i am unable to access your code as well as mine
import java.util.*;
public class Main {
public static int primeFac(int n,int k){
HashMap<Integer,Integer> a= new HashMap();
int flag=0;
while (n%2==0)
{
if(flag==0){
a.put(2,0);flag=1;}
a.put(2,a.get(2)+1);
n /= 2;
}
for (int i = 3; i <= Math.sqrt(n); i+= 2)
{ flag=0;
while (n%i == 0)
{
if(flag==0){
a.put(i,0);flag=1;}
a.put(i,a.get(i)+1);
n /= i;
}
}
if (n > 2)
{a.put(n,1);}
int arr[]=new int[k+1];
for(int i=k;i>=2;i--){
int d=i;
for(Integer f:a.keySet()){
while(d%f==0){
d=d/f;
arr[f]++;
}
}
}
int min=Integer.MAX_VALUE;
for(Integer f:a.keySet()){
int count=arr[f]/ a.get(f);
if(count<min){
min=count;
}
}
return min;
}
public static void main(String args[]) {
Scanner sc= new Scanner(System.in);
int t=sc.nextInt();
while(t–>0){
int n=sc.nextInt();
int k=sc.nextInt();
int x= primeFac(k,n);
System.out.println(x);
}
}
}
my code
unable to accesss your code
// / CPP program to find the largest power
// of k that divides n!
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// To find the power of a prime p in
// factorial N
ll findPowerOfP(ll n, ll p)
{
ll count = 0;
ll r=p;
while (r <= n) {
// calculating floor(n/r)
// and adding to the count
count += (n / r);
// increasing the power of p
// from 1 to 2 to 3 and so on
r = r * p;
}
return count;
}
// returns all the prime factors of k
vector<pair<ll, ll> > primeFactorsofK(ll k)
{
// vector to store all the prime factors
// along with their number of occurrence
// in factorization of k
vector<pair<ll, ll> > ans;
for (ll i = 2; k != 1; i++) {
if (k % i == 0) {
ll count = 0;
while (k % i == 0) {
k = k / i;
count++;
}
ans.push_back(make_pair(i, count));
}
}
return ans;
}
// Returns largest power of k that
// divides n!
ll largestPowerOfK(ll n, ll k)
{
vector<pair<ll, ll> > vec;
vec = primeFactorsofK(k);
ll ans = INT_MAX;
for (ll i = 0; i < vec.size(); i++)
// calculating minimum power of all
// the prime factors of k
ans = min(ans, findPowerOfP(n,
vec[i].first) / vec[i].second);
return ans;
}
// Driver code
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
ll t;
cin>>t;
while(t–){
ll n,k;
cin>>n>>k;
cout << largestPowerOfK(n, k) << endl;
// cout << largestPowerOfK(10, 9) << endl;
}
}
check your network connection
// To find the power of a prime p in
// factorial N
ll findPowerOfP(ll n, ll p)
{
ll count = 0;
ll r=p;
while (r <= n) {
// calculating floor(n/r)
// and adding to the count
count += (n / r);
// increasing the power of p
// from 1 to 2 to 3 and so on
r = r * p;
}
return count;
}
pls explain how this function works unable to get
i got my above question thanks …
resolved thanks