Problem 11621 Small Factors，最小因數

要先求出只有 2 和 3 因數的數值，將這些數值排序， C 語言程式碼如下：

int factor[1000] = {0}, index = 0, tmp, sIndex = 0;
void create()
{
    int k; 
    long long int i, j;
    for (i = 1; i < 2147483648LL; i *= 2)
        for (j = 1; j < 2147483648LL; j *= 3)
        {
            if (i * j  > 2147483648LL) break;
            factor[index ++] = i * j;
            for (k = index - 1; k >= 1; k --)
            {
                if (factor[k] < factor[k - 1])
                {
                    tmp = factor[k];
                    factor[k] = factor[k - 1];
                    factor[k - 1] = tmp;         
                }
                else break;
            }
        }
}

再來讀入一個 n 值，再 factor 陣列找出大於此數的最小數值，所以我們用「二分搜尋法」來實作，C 語言程式碼如下：

void location(int x, int low, int high)
{
    sIndex = 0;
    if (low > high) {sIndex = (low + high) / 2 + 1; return ;} 
    else 
    {
        int mid = 0;
        mid = (low + high) / 2;
        if (x == factor[mid]) {sIndex = mid; return ;} 
        else if (x < factor[mid]) location(x, low, mid - 1);
        else location(x, mid + 1, high);
    }
}

最後，只需在主程式呼叫：

location(n, 0, index - 1);
printf("%d\n", factor[sIndex]);

By David.K

p11621題目連結
回ACM題庫目錄
回首頁