gistfile1.txt

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<unsigned int> primes;
vector<unsigned int> p;
unsigned int get(unsigned int n, unsigned int p) {
	unsigned int res = 0;
	for (unsigned int power = p ; power <= n ; power *= p){
		res += n/power;
	}
	return res;// + get(n-1,p);
}

unsigned int pows(unsigned int n, unsigned int p) {
	unsigned int x = 0;
	while (n%p == 0) {
		n /= p;
		++x;
	}
	return x;
}

int main() {
	unsigned int m, n;
	unsigned int root;
	bool found;
	for (unsigned int i=2;i<=200000;i++) {
		root = int(sqrt(i))+1;
		found = false;
		for (unsigned int j = 0; j < primes.size() && primes[j] < root; ++j){
			if (i % primes[j] == 0) {
				found=true;
				break;
			}
		}
		if(!found)
			primes.push_back(i);
	}
	while (cin >> m >> n) {
		found = true;
		for (unsigned int i = 0; i < primes.size(); ++i) {
			if (!(n % primes[i])) {
				p.push_back(primes[i]);
			}
		}
		for (unsigned int i = 0; i < p.size(); ++i) {
			if (n % p[i] == 0) {
				if (get(m, p[i]) < pows(n, p[i])) {
					found = false;
					break;
				}
			}
		}
		if (found) cout << n << " divides " << m <<"!\n";
		else cout << n << " does not divide " << m <<"!\n";
	}
	system("pause");
	return 0;
}