最多约数问题-题解(C语言代码)

#include <stdio.h>
#include <malloc.h>
int main(void) {
    int N = 5e6 + 10;
    int *n = (int *)calloc(N, sizeof(int));
    int *p = (int *)calloc(N, sizeof(int));
    int *d = (int *)calloc(N, sizeof(int));
    int i = 0, j = 0, a = 0, b = 0, max = 1, t = 0;
    scanf("%d %d", &a, &b);
    for (i = 2; i <= b; ++i) {
        if (!p[i]) {
            n[t++] = i;
            p[i] = 2;
            d[i] = 2;
        }
        for (j = 0; j<t&&i*n[j]<=b; ++j) {
            p[i*n[j]] = 2;
            d[i*n[j]] = d[i]*2;
            if (0 == i%n[j]) {    //此时的n[j]就是质因数分离法中的分离的第一项中的底数,也就是一个质数 
                p[i*n[j]] = p[i]+1;
                d[i*n[j]] = d[i]/p[i]*p[i*n[j]];
                break;
            }
        }
        if (i >= a) {
            max = max>d[i]?max:d[i];
        }
    }
    printf("%d\n", max);
    free(p);
    free(n);
    free(d);
    return 0;
}