#include <iostream>
#include <cmath>
#include <vector>
#include <omp.h>
using namespace std;
bool isPrime(int n) {
if (n <= 1)
return false;
if (n == 2)
return true;
if (n % 2 == 0)
return false;
for (int i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int numProcs, size;
cout << "Num Processes: ";
cin >> numProcs;
cout << "Size: ";
cin >> size;
vector<bool> primes((size - 2) / 2 + 1, false); // The total number of prime numbers in the primes array, as it is only odd numbers starting from 3
#pragma omp parallel for schedule(dynamic) num_threads(numProcs)
for (int i = 3; i <= size; i += 2) {
if (isPrime(i)) {
primes[(i - 3) / 2] = true;
}
}
cout << "Prime numbers up to " << size << ":\n";
cout << 2 << " "; // Since 2 is the only even prime number
for (int i = 0; i < primes.size(); i++) {
if (primes[i]) {
cout << i * 2 + 3 << " ";
}
}
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxvbXAuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzUHJpbWUoaW50IG4pIHsKICAgIGlmIChuIDw9IDEpIAogICAgICAgIHJldHVybiBmYWxzZTsKICAgIGlmIChuID09IDIpIAogICAgICAgIHJldHVybiB0cnVlOwogICAgaWYgKG4gJSAyID09IDApIAogICAgICAgIHJldHVybiBmYWxzZTsKCiAgICBmb3IgKGludCBpID0gMzsgaSA8PSBzcXJ0KG4pOyBpICs9IDIpIHsKICAgICAgICBpZiAobiAlIGkgPT0gMCkgcmV0dXJuIGZhbHNlOwogICAgfQogICAgcmV0dXJuIHRydWU7Cn0KCmludCBtYWluKCkgewogICAgaW50IG51bVByb2NzLCBzaXplOwogICAgY291dCA8PCAiTnVtIFByb2Nlc3NlczogIjsKICAgIGNpbiA+PiBudW1Qcm9jczsKICAgIGNvdXQgPDwgIlNpemU6ICI7CiAgICBjaW4gPj4gc2l6ZTsKCiAgICB2ZWN0b3I8Ym9vbD4gcHJpbWVzKChzaXplIC0gMikgLyAyICsgMSwgZmFsc2UpOyAvLyBUaGUgdG90YWwgbnVtYmVyIG9mIHByaW1lIG51bWJlcnMgaW4gdGhlIHByaW1lcyBhcnJheSwgYXMgaXQgaXMgb25seSBvZGQgbnVtYmVycyBzdGFydGluZyBmcm9tIDMKCiNwcmFnbWEgb21wIHBhcmFsbGVsIGZvciBzY2hlZHVsZShkeW5hbWljKSBudW1fdGhyZWFkcyhudW1Qcm9jcykKICAgIGZvciAoaW50IGkgPSAzOyBpIDw9IHNpemU7IGkgKz0gMikgewogICAgICAgIGlmIChpc1ByaW1lKGkpKSB7CiAgICAgICAgICAgIHByaW1lc1soaSAtIDMpIC8gMl0gPSB0cnVlOwogICAgICAgIH0KICAgIH0KCiAgICBjb3V0IDw8ICJQcmltZSBudW1iZXJzIHVwIHRvICIgPDwgc2l6ZSA8PCAiOlxuIjsKICAgIGNvdXQgPDwgMiA8PCAiICI7IC8vIFNpbmNlIDIgaXMgdGhlIG9ubHkgZXZlbiBwcmltZSBudW1iZXIKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcHJpbWVzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgaWYgKHByaW1lc1tpXSkgewogICAgICAgICAgICBjb3V0IDw8IGkgKiAyICsgMyA8PCAiICI7CiAgICAgICAgfQogICAgfQogICAgY291dCA8PCBlbmRsOwoKICAgIHJldHVybiAwOwp9