朴素筛法求质数

1. 求出前sqrt(num)个质数, num < 1e9 所以n 约等于 3*1e4，这里取4*1e4
2. 枚举字符串，如果该数不能整除primes中的所有质数，则该数也是质数。

C++ 代码

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

const int MAX_L = 1010;


unordered_map<int, bool> isNotPrime;
vector<int> primes;

void GetPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (isNotPrime[i] == false) {
            primes.push_back(i);
            for (int j = i + i; j < n; j += i) {
                isNotPrime[j] = true;
            }
        }
    }
}

bool IsPrime(int num) {
    for (int i = 0; primes[i] * primes[i] <= num; i++) {
        if (num % primes[i] == 0) return false;
    }
    return true;
}

int main() {
    int l, k;
    string str;
    cin >> l >> k >> str;
    GetPrime(40000);
    int flag = false;
    for (int i = 0; i + k <= str.length(); i++) {
        int num = stoi(str.substr(i, k));
        if (IsPrime(num)) {
            printf("%s\n", str.substr(i, k).c_str());
            flag = true;
            break;
        }
    }
    if (!flag) puts("404");
    return 0;
}