日常雜物間

#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAXN 100005

int vis[MAXN], prime[10000], num;

void get_prime()
{
    num = 0;
    memset(vis, 0, sizeof(vis));
    int i, j;
    for (i = 2; i < MAXN; i++)
    {
        if (!vis[i])
        {
            prime[num++] = i;
            for (j = i + i; j < MAXN; j += i)
                vis[j] = 1;
        }
    }
}

int Cal(int w, int p)
{
    int ans = 0;
    while (w)
    {
        w /= p;
        ans += w;
    }
    return ans;
}

int judge(int n, int m)
{
    int i;
    int k = (int)sqrt(m + 0.5);
    for (i = 0; i < num && prime[i] <= k; i++)
    {
        if (m % prime[i] == 0)
        {
            int cnt = 0;
            while (m % prime[i] == 0)
            {
                cnt++;
                m /= prime[i];
            }
            if (Cal(n, prime[i]) < cnt) return 0;
        }
    }
    if (m > 1 && n < m) return 0;
    return 1;
}

int main()
{
    int n, m;
    get_prime();
    while (scanf("%d %d", &n, &m) != EOF)
    {
        if (judge(n, m))
            printf("%d divides %d!\n", m, n);
        else
            printf("%d does not divide %d!\n", m, n);
    }
    return 0;
}