UVa 10139 - Factovisors

// UVa 10139 - Factovisors
#include <iostream>
#include <vector>
#include <string.h>
#include <stdio.h>
using namespace std;

#define integer unsigned long long

int main() {
	bool isprime[65536];
	memset(isprime, true, sizeof(isprime));
	vector<integer> prime;
	for (integer i = 2; i < 65536; i++)
		if (isprime[i]) {
			prime.push_back(i);
			for (integer j = i * i; j < 65536; j += i)
				isprime[j] = false;
		}
	integer n, mm;
	while (cin >> n >> mm) {
		vector<integer> factor, expo;
		integer m = mm;
		for (int i = 0; i < prime.size() && m > 1; i++) {
			if (m % prime[i] == 0) {
				factor.push_back(prime[i]);
				expo.push_back(0);
				while (m % prime[i] == 0) {
					expo[expo.size() - 1]++;
					m /= prime[i];
				}
			}
		}
		if (m > 1) {
			factor.push_back(m);
			expo.push_back(1);
		}
		bool divides = (mm != 0);
		for (int i = 0; i < factor.size(); i++) {
			integer j = n;
			int count = 0;
			while (j >= factor[i]) {
				j /= factor[i];
				count += j;
			}
			if (count < expo[i]) {
				divides = false;
				break;
			}
		}
		if (divides)
			printf("%llu divides %llu!\n", mm, n);
		else
			printf("%llu does not divide %llu!\n", mm, n);
	}
	return 0;
}