UVALive2247 Prime Digital Roots

Myth丶恋晨 2022-01-09 10:53 118阅读 0赞

**Regionals 2001 >> South Pacific**

**问题链接**：[UVALive2247 Prime Digital Roots][]。基础训练题，用C语言编写程序。

**问题分析**：

数根是指整数的各个位的数字之和。如果其和为１位整数，则为结果；如果其和为多位整数，则再将各位数字相加，直到其和为１位数为止。

但是，这个题有点不一样，输入的数只要是素数就可以了，如果不是素数就计算其数根，数根（可以是多位整数）是素数也就可以了。必要时，需要重复计算数根，直到只剩下１位为止。

**程序说明**：

需要说明的有以下几点：

1.输入输出需要用６４位整数，所以用了long long类型；

2.函数getroot()调用层次不会太深，所以使用递归调用；

3.输出时，两项宽度均为7，中间有个空格。

**参考链接**：[HDU1013 Digital Roots（解法二）][HDU1013 Digital Roots]。

AC的C语言程序如下：

/* UVALive2247 Prime Digital Roots */
    
    #include <stdio.h>
    #include <math.h>
    
    /* 试除法判断一个数是否为素数 */
    int isprime(long long n)
    {
        if(n == 2 || n == 3)
            return 1;
    
        if((n & 1) == 0 || n == 1)  /* 偶数：n % 2 == 0 */
            return 0;
    
        long end = sqrt(n), i;
        for(i=3; i<=end; i+=2) {
            if(n % i == 0)
                break;
        }
    
        return i > end ? 1 : 0;
    }
    
    long getroot(long val)
    {
        int root = 0;
    
        while(val) {
            root += val % 10;
    
            val /= 10;
        }
    
        while(root >= 10 && !isprime(root))
            root = getroot(root);
    
        return root;
    }
    
    int main(void)
    {
        long long n;
        int root, okflag;
    
        while(scanf("%lld", &n) != EOF) {
            /* 判定结束条件 */
            if(n == 0)
                break;
    
            /* 计算数根 */
            if(isprime(n)) {
                root = n;
                okflag = 1;
            } else {
                root = getroot(n);
                okflag = isprime(root);
            }
    
            if(okflag)
                printf("%7lld%8d\n", n, root);
            else
                printf("%7lld    none\n", n);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tigerisland/p/7564589.html

[UVALive2247 Prime Digital Roots]: http://acm.hust.edu.cn/vjudge/problem/42445
[HDU1013 Digital Roots]: http://blog.csdn.net/tigerisland45/article/details/51915714