本帖最后由 永恒的蓝色梦想 于 2021-2-20 20:38 编辑
C++ 322ms#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
template<size_t size, typename T>
void euler_sieve(bool (&is_prime)[size], vector<T>& primes) {
T i, k;
memset(is_prime, -1, size);
is_prime[0] = is_prime[1] = 0;
for (T i = 2; i < size; i++) {
if (is_prime[i]) {
primes.push_back(i);
}
for (T j : primes) {
k = i * j;
if (k >= size) {
break;
}
is_prime[k] = false;
if (!(i % j)) {
break;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
constexpr unsigned int UPPER_BOUND = 100000000;
static bool is_prime[UPPER_BOUND / 2];
vector<unsigned int> primes;
unsigned int i, j, result = 0;
euler_sieve(is_prime, primes);
for (i = 0; primes[i] * primes[i] < UPPER_BOUND; result += ++i);
for (j = i; i < primes.size(); i++) {
while (primes[i] * primes[j] >= UPPER_BOUND) {
j--;
}
result += j;
result++;
}
cout << result << endl;
return 0;
}
|