# Factovisors

Factovisors

The factorial function, n! is defined as follows for all non-negative integers n:

0! = 1
n! = n x (n - 1)! (n > 0)

We say that a divides b if there exists an integer k such that

k x a = b

The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 231.

For each input line, output a line stating whether or not m divides n!, in the format shown below.

``````6 9
6 27
20 10000
20 100000
1000 1009

``````

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

``````#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
long LEN = 1 << 16;
vector<long> primes;
void init()
{
bool filter[LEN];
for ( int i=0; i<LEN; i++ ) filter[i] = true;
long max = (long)sqrt(LEN)+1;
for ( int i=2; i<=max; i++ )
if ( filter[i] )
for ( int j=2*i; j<LEN; j+=i )
filter[j] = false;
for ( int i=2; i<LEN; i++ )
if ( filter[i] )
primes.push_back(i);
}
bool divByP2Kth(long p, long k, long n)
{
if ( k==0 ) return true;
long cnt = 0;
for ( long i=p; i<=n; i*=p )
{
cnt += n/i;
if ( cnt >= k ) return true;
}
return false;
}
bool divide(long m, long n)
{
if ( m==0 )return false;
else if (m==1)return true;
for (unsigned int i=0; i<primes.size(); i++ )
{
long p =primes.at(i), k = 0;
while ( m%p == 0 )
{
k++;
m /= p;
}
if ( ! divByP2Kth(p,k,n) ) return false;
if ( m==1 ) break;
}
if ( m>1 && ! divByP2Kth(m,1,n) ) return false;
return true;
}
int main()
{
init();
long n, M;
while (cin >> n >> M)
{
bool ok = divide(M,n);
if (ok)cout << M << " divides " << n << "!" << endl;
else cout << M << " does not divide " << n << "!" << endl;
}
return 0;
}
``````

``````#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
long LEN = 1 << 16;
vector<long> primes;
void init()
{
bool filter[LEN];
for ( int i=0; i<LEN; i++ ) filter[i] = true;
long max = (long)sqrt(LEN)+1;
for ( int i=2; i<=max; i++ )
if ( filter[i] )
for ( int j=2*i; j<LEN; j+=i )
filter[j] = false;
for ( int i=2; i<LEN; i++ )
if ( filter[i] )
primes.push_back(i);
}
bool divByP2Kth(long p, long k, long n)
{
if ( k==0 ) return true;
long cnt = 0;
for ( long i=p; i<=n; i*=p )
{
cnt += n/i;
if ( cnt >= k ) return true;
}
return false;
}
bool divide(long m, long n)
{
if ( m==0 )return false;
else if (m==1)return true;
for (unsigned int i=0; i<primes.size(); i++ )
{
long p =primes.at(i), k = 0;
while ( m%p == 0 )
{
k++;
m /= p;
}
if ( ! divByP2Kth(p,k,n) ) return false;
if ( m==1 ) break;
}
if ( m>1 && ! divByP2Kth(m,1,n) ) return false;
return true;
}
int main()
{
init();
long n, M;
while (cin >> n >> M)
{
bool ok = divide(M,n);
if (ok)cout << M << " divides " << n << "!" << endl;
else cout << M << " does not divide " << n << "!" << endl;
}
return 0;
}
``````