Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1080
The factorial function, n! is defined thus for n a non-negative integer: 0! = 1 n! = n × (n − 1)! (n > 0) We say that a divides b if there exists an integer k such that k × a = b Input The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 231 . Output For each input line, output a line stating whether or not m divides n!, in the format shown below.
Sample Input 6 9 6 27 20 10000 20 100000 1000 1009
Sample Output 9 divides 6! 27 does not divide 6! 10000 divides 20! 100000 does not divide 20! 1009 does not divide 1000!
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
const int N = 50000;
void sieve(){
bitset < N> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = false;
for(long long i=2;i < N;i++){
if(isPrime[i]){
primes.push_back(i);
for(long long j=i*i;j<N;j+=i)
isPrime[j] = false;
}
}
}
// exponent of a prime p in n!
int get_powers(int n, int p) {
int res = 0;
for(int power=p; power < =n; power*=p)
res += n/power;
return res;
}
bool canDivide(int n, int m){
for(int pidx = 0; pidx < primes.size()
&& primes[pidx]*primes[pidx] <= m; pidx++){
int cntFactor = 0;
while(m%primes[pidx] == 0) {
cntFactor++;
m /= primes[pidx];
}
int cntFactorN = get_powers(n, primes[pidx]);
if(cntFactorN < cntFactor> return false;
}
// not fully factored and m is larger
if(m != 1 && m > n) return false;
return true;
}
int main() {
sieve();
int n,m;
while(scanf("%d %d",&n,&m) != EOF){
if(canDivide(n, m))
printf("%d divides %d!\n", m, n);
else
printf("%d does not divide %d!\n", m, n);
}
}Input
6 27
20 10000
20 100000
1000 1009
Output
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!
Demonstration
UVA Online Judge solution - 10139 - Factovisors - UVA Online Judge solution in C,C++,Java