Nepoužívajte Avast

Kód hľadania:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <omp.h>

#define SEGMENT_SIZE 1048576 // 1 MB segment ideálny pre L2/L3 Cache jadier
#define MAX_GAP 1500
#define RAM_LIMIT_MB 200 // Navýšené na 200 MB pre rýchlejšie disky na stolnom PC

int main() {
long long int CIELOVY_POCET;
int percenta_cpu;

printf("--- MAXIMALNA PARALELIZACIA S KONTROLOU VYKONU ---\n");
printf("Zadaj cielovy pocet prvocisiel (napr. 1000000000): ");
if (scanf("%lld", &CIELOVY_POCET) != 1 || CIELOVY_POCET <= 0) return 1;

printf("Zadaj kolko %% vykonu CPU chces pouzit (1 - 100): ");
if (scanf("%d", &percenta_cpu) != 1 || percenta_cpu < 1 || percenta_cpu > 100) {
printf("Neplatne percento výkonu.\n");
return 1;
}

double start_time = omp_get_wtime();

// 1. Nastavenie počtu jadier podľa zvolených percent
int max_dostupnych_jadier = omp_get_max_threads();
int pocet_vlakien = (int)ceil((max_dostupnych_jadier * percenta_cpu) / 100.0);
if (pocet_vlakien < 1) pocet_vlakien = 1;

// Prikážeme OpenMP použiť len určený počet jadier
omp_set_num_threads(pocet_vlakien);
printf("\nAlokujem %d z %d jadier CPU (zvolenych %d%% vykonu)...\n",
pocet_vlakien, max_dostupnych_jadier, percenta_cpu);

// 2. Odhad horného číselného limitu na základe požadovaného počtu
long long int MAX_CISLO = (CIELOVY_POCET < 10) ? 100 : (long long int)(CIELOVY_POCET * log(CIELOVY_POCET) * 1.2) + 1000;

// Predsito pre generovanie základných prvočísel
int sqrt_limit = (int)sqrt(MAX_CISLO);
std::vector<char> is_prime_small(sqrt_limit + 1, 1);
for (int p = 2; p * p <= sqrt_limit; p++) {
if (is_prime_small[p]) {
for (int i = p * p; i <= sqrt_limit; i += p) is_prime_small[i] = 0;
}
}
std::vector<int> primes;
for (int p = 2; p <= sqrt_limit; p++) if (is_prime_small[p]) primes.push_back(p);

// Globálne premenné a štatistiky
long long int globalny_pocet_celkovo = 0;
long long int globalna_statistika_medzier[MAX_GAP] = {0};
long long int globalne_posledne_prvocislo = 2;

// Zastavovací príznak pre vlákna, ak už máme dosť prvočísel
bool koniec_vsetko = false;

// 3. PARALELNA ZÓNA
#pragma omp parallel
{
int thread_id = omp_get_thread_num();
int num_threads = omp_get_num_threads();

// Rozdelenie megablokov podla REÁLNE spusteného počtu vlákien
long long int rozsah_jedneho_jadra = (MAX_CISLO - 3) / num_threads;
long long int thread_low = 3 + thread_id * rozsah_jedneho_jadra;
long long int thread_high = (thread_id == num_threads - 1) ? MAX_CISLO : (thread_low + rozsah_jedneho_jadra - 1);

if (thread_low % 2 == 0) thread_low++;

char t_filename[32];
sprintf(t_filename, "tmp_thread_%d.bin", thread_id);
FILE *f_bin = fopen(t_filename, "wb");

long long int max_v_ram = (RAM_LIMIT_MB * 1024LL * 1024LL) / sizeof(long long int);
long long int *ram_buffer = (long long int *)malloc(max_v_ram * sizeof(long long int));
long long int miestna_statistika_medzier[MAX_GAP] = {0};

long long int miestny_pocet = 0;
long long int posledne_miestne_prvocislo = 0;
int v_ram = 0;

long long int low = thread_low;
while (low <= thread_high && !koniec_vsetko) {
long long int high = low + SEGMENT_SIZE - 1;
if (high > thread_high) high = thread_high;

std::vector<char> segment(high - low + 1, 1);

for (size_t i = 0; i < primes.size(); i++) {
int p = primes[i];
long long int start = (low + p - 1) / p * p;
if (start < (long long int)p * p) start = (long long int)p * p;
if (start % 2 == 0) start += p;
for (long long int j = start; j <= high; j += 2 * p) {
segment[j - low] = 0;
}
}

for (long long int n = low; n <= high; n += 2) {
if (segment[n - low]) {
// Poistka: Ak iné vlákno medzitým naplnilo celkový počet, končíme zápis
if (koniec_vsetko) break;

if (posledne_miestne_prvocislo != 0) {
long long int medzera = n - posledne_miestne_prvocislo;
if (medzera < MAX_GAP) miestna_statistika_medzier[medzera]++;
}
posledne_miestne_prvocislo = n;

ram_buffer[v_ram++] = n;
miestny_pocet++;

if (v_ram >= max_v_ram) {
fwrite(ram_buffer, sizeof(long long int), v_ram, f_bin);
v_ram = 0;
}
}
}

// Kontrola ukončenia: sčítame priebežný bezpečný stav (len občas, aby sme nespomaľovali CPU)
if (low % (SEGMENT_SIZE * 20) == 3) {
long long int aktualny_globalny_stav = 0;
#pragma omp atomic read
aktualny_globalny_stav = globalny_pocet_celkovo;

if (aktualny_globalny_stav >= CIELOVY_POCET) {
koniec_vsetko = true;
}

if (thread_id == 0) {
double percenta = (double)(low - thread_low) * 100.0 / (thread_high - thread_low);
if (percenta > 100.0) percenta = 100.0;
printf("\rVlakno 0 Progres: %.1f %% | Spracovava sa... ", percenta);
fflush(stdout);
}
}

low += SEGMENT_SIZE;
}

if (v_ram > 0) fwrite(ram_buffer, sizeof(long long int), v_ram, f_bin);
fclose(f_bin);
free(ram_buffer);

// Bezpečné sčítanie výsledkov z tohto jadra
#pragma omp critical
{
globalny_pocet_celkovo += miestny_pocet;
for (int i = 0; i < MAX_GAP; i++) {
globalna_statistika_medzier[i] += miestna_statistika_medzier[i];
}
if (posledne_miestne_prvocislo > globalne_posledne_prvocislo) {
globalne_posledne_prvocislo = posledne_miestne_prvocislo;
}
}
} // Koniec paralelnej zóny

printf("\rVlakno 0 Progres: 100.0 %%\n");
printf("Vypocty ukoncene. Spajam a orezavam docasne subory na presny pocet...\n");

// 4. Spojenie súborov a presné orezanie na požadovaný cieľový počet
FILE *f_vysledok = fopen("tmp.bin", "wb");
long long int cislo_dva = 2;
fwrite(&cislo_dva, sizeof(long long int), 1, f_vysledok);

long long int zapisane_celkovo = 1; // Započítaná dvojka

for (int i = 0; i < pocet_vlakien; i++) {
char t_filename[32];
sprintf(t_filename, "tmp_thread_%d.bin", i);
FILE *f_in = fopen(t_filename, "rb");
if (f_in) {
long long int buffer_spojenia[4096];
size_t precitane;
while ((precitane = fread(buffer_spojenia, sizeof(long long int), 4096, f_in)) > 0) {
for (size_t j = 0; j < precitane; j++) {
if (zapisane_celkovo < CIELOVY_POCET) {
fwrite(&buffer_spojenia[j], sizeof(long long int), 1, f_vysledok);
zapisane_celkovo++;
// Aktualizujeme posledné reálne zapísané prvočíslo
globalne_posledne_prvocislo = buffer_spojenia[j];
} else {
break;
}
}
if (zapisane_celkovo >= CIELOVY_POCET) break;
}
fclose(f_in);
remove(t_filename); // Vyčistenie disku
}
}
fclose(f_vysledok);

// Zápis štatistiky
FILE *f_stat = fopen("statistika_medzier.txt", "w");
fprintf(f_stat, "Medzera;Pocet_vyskytov\n");
for (int i = 1; i < MAX_GAP; i++) {
if (globalna_statistika_medzier[i] > 0) {
fprintf(f_stat, "%d;%lld\n", i, globalna_statistika_medzier[i]);
}
}
fclose(f_stat);

printf("\n=== HOTOVO ===\n");
printf("Celkovy cas: %.2f s\n", omp_get_wtime() - start_time);
printf("Presny pocet zapisanych prvocisiel: %lld\n", zapisane_celkovo);
printf("Posledne prvocislo (index %lld): %lld\n", zapisane_celkovo, globalne_posledne_prvocislo);

printf("\nStlac Enter pre ukoncenie...");
fflush(stdout);
getchar(); getchar();

return 0;
}