题解

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1093;
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
vector<int> sieve(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= n; ++i) {
    if (isPrime[i]) { 
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false; 
        }
    }
} 
vector<int> primes;
for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) { 
        primes.push_back(i);
    }
} 
return primes; 

}
int main() {
int n;
cin >> n;
vector<int> primes = sieve(n);
int totalSum = 0;
for (int prime : primes) {
totalSum = (totalSum + digitSum(prime)) % MOD;
}
cout << totalSum << endl;
return 0;
}