Problem 10539 Almost Prime Numbers，只一質數整除的數

此題是要求出整數 low 和整數 high 之間的只一質數整除的數，首先得先求出 1 ~ sqrt(1000000000000) 之間只一質數整除的數，宣告一 prime[1000000] 陣列以存放每一個數能被幾個質數整除的數量：

#define MAXLEN 1000000

int prime[MAXLEN + 1] = {0};

再來將每一個 prime[i] = 0 的數，依 i * 2、i * 3、i * 4、....、i * n (i * n <= 1000000)的索引值累加 1，如遇 prime[i] > 0 則跳過不做，寫成 C 語言程式碼如下：

int i, j;
for (i = 2; i <= MAXLEN; i ++)
    if(prime[i] > 0) continue;
    else
        for (j = 2; i * j <= MAXLEN; j ++)
            prime[i * j] ++;

如此執行完，prime[i] = 1 的 i 值，即為 Almost Prime Number。而當 high <= 10⁶ 可以直接算出 prime[i] = 1 有幾個，但當 high > 10⁶ 則需創建另一個陣列來存放 prime[i] = 0 質數的次方，這些次方需小於 10¹²，寫成 C 語言程式碼如下：

unsigned long long int ten12 = (long long int)1e12;
unsigned long long int prime_tbl[80070] = {0};

unsigned long long int p;
int index = 0;
for (i = 2; i <= MAXLEN; i ++)
    if (prime[i] == 0)
    {
        p = i;        
        while (p < ten12)
        {
            if (p != i) prime_tbl[index ++] = p;
            p *= i; 
        }
    }

創建好質數次方表後，再將質數次方表排序，而我使用前幾篇所用過的一種排序法，Mergesort（合併排序法），而這種排序請參考 Problem 10810 裡的文章的解說，相信很快就可以排序好。當 high > 10⁶，就將 low 恰大於等於 prime[i] 的索引 lowIndex ，和 high 恰大於等於 prime[i] 的索引 highIndex 相減，答案就出來了，但 low 剛好等於 prime[i] 時，答案要多加 1。寫成 C 語言程式碼如下：

int i, n, count, lowIndex, highIndex;
unsigned long long int low, high;
scanf("%d", &n);
while (n --)
{
    count = 0;
    lowIndex = -1, highIndex = -1;
    scanf("%lld %lld", &low, &high);
    if (high <= MAXLEN)
    {
        for (i = low; i <= high; i ++)
            if (prime[i] == 1) count ++;
    }
    else 
    {
        for (i = 80069; i >= 0; i --)
        {
            if (prime_tbl[i] <= low && lowIndex == -1)
            {
                if (prime_tbl[i] == low) count ++;             
                lowIndex = i;
                break;
            }
            if (prime_tbl[i] <= high && highIndex == -1)        
                highIndex = i;
        } 
        count += highIndex - lowIndex;
    }
    printf("%d\n", count);        
}

By David.K

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