UVA - 10789 - Prime Frequency（素数打表）

浅浅的花香味﹌ 2022-06-07 00:21 191阅读 0赞

题意是给出0-9，A-Z，a-z，组成的字符串，如果字符的个数是素数就输出这个字符。  
例如ABCC中的C的个数是素数，那么输出C；  
首先素数打表，剩下的就是如何储存每个字符的个数了，我们可以利用ascll码。  
每个字母有不同的ascll码，我们让每个字符减去0的ascll码，为什么是0呢，因为最小的ascll就是0，这样数组就是从0开始的（‘0’-‘0’= 0），这样可以减少数组的大小，节约内存；

#include<iostream>
    #include<cmath>
    #include<cstring>
    #define MAXN 200
    
    using namespace std;
    
    int a[MAXN];//储存每个字母的个数
    bool vis[2100];//素数打表
    char str[2100];//储存输入的字符串
    
    void checkprime(int n) {
       //素数打表没啥好说的
        int m = sqrt(n+0.5);
        memset(vis, true, sizeof(vis));
        vis[0] = vis[1] = false;
        for(int i = 2; i <= m; i++) {
            if(vis[i]) {
                for(int j = i*i; j <= n; j+=i) {
                    vis[j] = false;
                }
            }
        }
    }
    
    int main() {
        checkprime(2100);//把表打好，如果全是一种字符的话最大2001个，打2100个足够了
        int t;
        scanf("%d", &t);
        for(int i = 1; i <= t; i++) {
            int flag = 1;
            memset(a, 0, sizeof(a));
            scanf("%s", str);
            int len = strlen(str);
            for(int i = 0; i < len; i++) {
                a[str[i] - '0']++;//减去0的ascll剩下的ascll码作为数组的下标
            }
            printf("Case %d: ", i);
            for(int i = 0; i <= 74; i++) {
                if(vis[a[i]]) {
                    printf("%c", i + '0');
                    flag = 0;//标记有没有输出过
                }
            }
            if(flag) printf("empty");
            printf("\n");
        } 
        return 0;
    }