Problem 10533 Digit Primes，質數中的質數

此題是需要找出質數中每位數字相加後，還能等於質數的傢伙。可以想見，在條件 0 < t1 <= t2 < 1000000 之下，最大的數也不過是 999999，判斷質數的數字為 54(9 + 9 + 9 + 9 + 9 + 9)，所以先建立一個質數表，只要輸入索引，立即可知此數是否為質數，C 語言程式碼如下：

int prime[55] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 
                 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
                 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
                 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 
                 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 
                 0, 0, 0, 1, 0};

定義一個整數 s 為 0，再來找出 1 ~ 1000000 之間的質數，並且將這些質數分解後並利用以上質數表判斷是否為質數，如是，則改為 ++ s；反之，改為 s。寫成 C 語言程式碼如下：

#define MAXLEN 1000000
int digitPrime[MAXLEN] = {0};

int makeprime(){
    int i, j, sum, n, s = 0;
    for(i = 2;i < MAXLEN; i ++)
    {  
        if(!digitPrime[i])
        {
            for(j = i + i; j < MAXLEN; j += i)
                digitPrime[j] = 1;
            sum = 0;
            n = i;
            while (n)
                sum += n % 10, n = n / 10;
            if (prime[sum])
            { ++ s; digitPrime[i] = s; }
            else digitPrime[i] = s;    
        }
        else digitPrime[i] = s;
    }
}

最後，主程式只須這樣寫：

int n, t1, t2, i, count;
scanf("%d", &n);
while (n --)
{
    count = 0;  
    scanf("%d %d", &t1, &t2);
    printf("%d\n", digitPrime[t2] - digitPrime[t1] + (digitPrime[t1] != digitPrime[t1 - 1]));
}

By David.K

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