ACM 294 Divisors

找因數。
跟ACM 160類似。

先做質因數分解，再用質因數分解的答案算出所有因數。
例如6是 2^1 * 3^1，所以6的所有因數為(1 + 1) * (1 + 1) = 4。
題目已經告訴我們1000000000中最多是192個因數。
所以會用到的質數一定小於192。
但這時候會有個問題，如果是給的值，是第193以後的質數怎麼辦？
因為質數只能被自己跟1整除，所以也不會被其他質數整除。
反正質數的因數就只有2個，所以質數也可以處理了。

老實說我一開始沒想到第193個質數之後的情況，
但寫出來的程式碼也誤打誤撞AC =.=，
可能測資過了，但程式碼還是要修。
後來終於找到一個想法跟我差不多的人寫得程式碼，
好厲害！他補完了我沒想到的部份：
連結

完整假設是這樣：
因為合數必定可以拆成兩個質數相乘。
如果存在一組質數，使得p1 * p2 > 1000000000，
而p1, p2之前的質數相乘都能 < 1000000000的話，
那麼在1000000000這些數中，
最多最多會用到的質數，就是比p1或p2小的質數，
這要怎麼證明呢？
因為合數n必定可以拆成a * b，
a跟b必有一數大於等於根號n，另一數小於等於根號n，
所以我們只要找等於根號n的那個質數即可。
大於等於根號n的質數不用找，因為a跟b都要考慮，
若一個是大於等於根號n，那另一個必定小於等於根號n，
如此，只要找到小於等於根號n的所有情況，
也就滿足所有情況了。
第3401個質數為31607，31607的平方為999002449，
第3402個質數為31627，31627的平方為1000267129。
所以最多最多會用到的質數就是第3401個質數為31607。

總結，
只要考慮能被前3402個質數整除即可，
再用質因數分解的方式去找所有質數即可。
若合數n最後不是等於1，表示存在一個質數p，
使得前3402個質數都無法整除此質數p。
這種情況也不用擔心，因為能整除質數數只有兩種，
1跟他自己。
所以再把答案 * 2即可。

/* ACM 294 Divisors
 * mythnc
 * 2011/11/17 12:13:07   
 * run time: 0.032
 */
#include <stdio.h>

#define MAXP  3402
#define TRUE  1
#define FALSE 0

typedef struct divisor {
    int number, count;
} Divisor;

typedef struct big {
    int number, sum;
} Big;

void findp(Divisor *);
Big maxn(Divisor *, int, int);
int dnumber(Divisor *, int);

int main(void)
{
    int head, tail;
    Big max;
    Divisor prime[MAXP];

    findp(prime);
    scanf("%*d");
    while (scanf("%d %d", &head, &tail) == 2) {
        max = maxn(prime, head, tail);
        printf("Between %d and %d, %d has a maximum of %d divisors.\n"
                , head, tail, max.number, max.sum);
    }
    return 0;
}

/* findp: find n primes */
void findp(Divisor *p)
{
    int count, i, j, flag;

    p[0].number = 2;
    count = 1;
    for (i = 3; count < MAXP; i += 2) {
        for (flag = TRUE, j = 3; j * j <= i; j++)
            if (i % j == 0) {
                flag = FALSE;
                break;
            }
        if (flag)
            p[count++].number = i;
    }
}

/* maxn: return the number which has the max divisors */
Big maxn(Divisor *p, int head, int tail)
{
    int i, number;
    Big max;

    max.number = head;
    max.sum = dnumber(p, head);
    for (i = head + 1; i < tail + 1; i++) {
        number = dnumber(p, i);
        if (max.sum < number) {
            max.sum = number;
            max.number = i;
        }
    }

    return max;
}

/* dnumber: return number of divisors of n */
int dnumber(Divisor *p, int n)
{
    int i, j, d;

    if (n == 1)
        return 1;

    for (i = 0; i < MAXP && n != 1; i++) {
        p[i].count = 0;
        while (n % p[i].number == 0) {
            n /= p[i].number;
            p[i].count++;
        }
    }

    for (d = 1, j = 0; j < i; j++)
        if (p[j].count != 0)
            d *= p[j].count + 1;

    if (n != 1)
        return d * 2;
    return d;
}