1.【第10期】专属内容.zip

/************************************************************************* > File Name: 2.prime_count.cpp > Author: huguang > Mail: hug@haizeix.com > Created Time: ************************************************************************/ #include <iostream> #include <cstdio> #include <cstdlib> #include <queue> #include <stack> #include <algorithm> #include <string> #include <map> #include <set> #include <vector> #include <thread> #include <mutex> using namespace std; #define BEGIN(name) namespace name { #define END(name) } #define MAX_N 5000000 #define TIME(func) { \ long long b = clock(); \ func;\ long long e = clock(); \ printf("%s run %lldms\n", #func, 1000 * (e - b) / CLOCKS_PER_SEC); \ } BEGIN(normal_count) int is_prime(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0) return 0; } return 1; } int main() { int cnt = 0; for (int i = 2; i <= MAX_N; i++) { cnt += is_prime(i); } cout << cnt << endl; return 0; } END(normal_count) BEGIN(prime_count_1) int is_prime(int x) { if (x <= 1) return 0; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return 0; } return 1; } void count_prime(int b, int e, int &ret) { ret = 0; for (int i = b; i <= e; i++) { ret += is_prime(i); } return ; } int main() { int batch = MAX_N / 10; int ret[10]; thread *threads[10]; for (int i = 0, j = 1; i < 10; i++, j += batch) { threads[i] = new thread(count_prime, j, j + batch - 1, ref(ret[i])); } for (int i = 0; i < 10; i++) { threads[i]->join(); } int ans = 0; for (auto x : ret) ans += x; cout << ans << endl; return 0; } END(prime_count_1) BEGIN(prime_count_2) int ans; mutex mutex_x; int is_prime(int x) { if (x <= 1) return 0; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return 0; } return 1; } void count_prime(int b, int e) { for (int i = b; i <= e; i++) { unique_lock<mutex> lock(mutex_x); ans += is_prime(i); } return ; } int main() { int batch = MAX_N / 10; int ret[10]; thread *threads[10]; ans = 0; for (int i = 0, j = 1; i < 10; i++, j += batch) { threads[i] = new thread(count_prime, j, j + batch - 1); } for (int i = 0; i < 10; i++) { threads[i]->join(); } cout << ans << endl; return 0; } END(prime_count_2) BEGIN(prime_count_3) int ans; int is_prime(int x) { if (x <= 1) return 0; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return 0; } return 1; } void count_prime(int b, int e) { for (int i = b; i <= e; i++) { int ret = is_prime(i); __sync_fetch_and_add(&ans, ret); } return ; } int main() { int batch = MAX_N / 10; int ret[10]; thread *threads[10]; ans = 0; for (int i = 0, j = 1; i < 10; i++, j += batch) { threads[i] = new thread(count_prime, j, j + batch - 1); } for (int i = 0; i < 10; i++) { threads[i]->join(); } cout << ans << endl; return 0; } END(prime_count_3) int main() { //normal_count::main(); //prime_count_1::main(); //prime_count_2::main(); prime_count_3::main(); return 0; }