判断一个数的回文

  • 偶数位数回文数（除了11）必定不是质数
  • 偶数肯定不是质数。这样至少排除一半多的数据量。
bool pdn(int x) {
    int y = x, num = 0;//int y=x,防止x被改变
    while (y != 0) {
        num = num * 10 + y % 10;//上一次数字的记录进位再加上下一位数
        y /= 10;
    }
    if (num == x) return true;
    else return false;
}

求一个数每位数字之和

int get(int x) {
    int ans = 0;
    for (; x; x /= 10) {
        ans += x % 10;
    }
    return ans;
}

判断一个数是不是质数

1.普通方法 O(sqrt(n))

bool isPrime(int x) {
    if(x == 1) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

2.线性筛 O(n)

  • 线性筛法并不是判定素数的，而是在线性时间内求出一个素数表，需要判定是否是素数的时候只要看该数是否在表内就可以瞬间知道是不是素数。
  • 适用于范围不是特别大，查询次数多的
const int maxn = 1e6 + 6;
int flag[maxn + 1], prime[maxn + 1], pnum;//flag[n] 表示n是否是素数，1是素数，0不是
//prime   中是所有的素数按从小到大排列、
//pnum  表示素数的个数
void createPrime() {
    pnum = 0;//初始化没有素数
    //先将所有数看做素数，然后开始筛选
    for (int i = 0; i <= maxn; i++) {
        flag[i] = 1;
    }
    //遍历筛去所有最大因数是i的合数
    for (int i = 2; i <= maxn; i++) {
        if (flag[i] == 1) {
            //把素数记录下来
            prime[pnum++] = i;
        }
        //遍历已知素数表中比i的最小素因数小的素数，并筛去合数
        for (int j = 0; j < pnum && prime[j] * i <= maxn; j++) {
            //筛去合数
            flag[prime[j] * i] = 0;
            if (i % prime[j] == 0)
                //找到i的最小素因数
                break;
        }
    }
}

int main() {
    createPrime();
    unordered_set<int> set;
    for (int i = 0; i < pnum; i++) {
        set.insert(prime[i]);
    }
    int n, m;
    sc(n);
    while (n--) {
        sc(m);
        if (set.find(m) != set.end()) printf("Yes\n");
        else printf("No\n");
    }
}

hhhhh