## Algorithm

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);
}
}``````
Copy The Code &

Input

cmd
6 9
6 27
20 10000
20 100000
1000 1009

Output

cmd
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!