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

#define MAX_CISLO 100000000 
#define MAX_GAP 500         

int main() 
{
    long long int globalna_statistika[MAX_GAP] = {0};
    
    printf("Analyzujem medzery na %d jadradch (Blokova analyza)...\n", omp_get_max_threads());

    // Paralelna sekcia
    #pragma omp parallel
    {
        // Kazde jadro ma svoju vlastnu lokalnu statistiku, aby sa nebili
        long long int lokalna_statistika[MAX_GAP] = {0};
        long long int lokalne_posledne = 0;
        int th_id = omp_get_thread_num();
        int num_th = omp_get_num_threads();

        // Rozdelime pracu na rovnomerne kusy
        long long int velkost_bloku = MAX_CISLO / num_th;
        long long int start = 3 + (th_id * velkost_bloku);
        long long int koniec = start + velkost_bloku;
        
        // Zarovnanie na neparne cislo
        if (start % 2 == 0) 
			start++;
        if (th_id == num_th - 1) 
			koniec = MAX_CISLO;

        // Najdenie prveho prvocisla v bloku pre startovaciu medzeru
        for (long long int n = start; n < koniec; n += 2) 
		{
            int je_prvo = 1;
            long long int odmocnina = (long long int)sqrt(n);
            for (long long int i = 3; i <= odmocnina; i += 2) 
			{
                if (n % i == 0) 
				{ 	je_prvo = 0; 
					break; 
				}
            }
            if (je_prvo) 
			{
                lokalne_posledne = n;
                break;
            }
        }

        // Hlavny vypocet v bloku
        for (long long int n = lokalne_posledne + 2; n < koniec; n += 2) 
		{
            int je_prvo = 1;
            long long int odmocnina = (long long int)sqrt(n);
            for (long long int i = 3; i <= odmocnina; i += 2) 
			{
                if (n % i == 0) 
				{	je_prvo = 0; 
				  	break; 
				}
            }
            if (je_prvo) 
			{
                long long int m = n - lokalne_posledne;
                if (m < MAX_GAP) 
					lokalna_statistika[m]++;
                lokalne_posledne = n;
            }
        }

        // Spojenie lokalnych statistik do jednej globalnej (bezpecne)
        #pragma omp critical
        {
            for (int i = 0; i < MAX_GAP; i++) 
			{
                globalna_statistika[i] += lokalna_statistika[i];
            }
        }
    }

    // Vypis vysledkov
    printf("\nHotovo. Najcastejsie medzery:\n");
    for (int g = 2; g < MAX_GAP; g += 2) 
	{
        if (globalna_statistika[g] > 10) // Vypiseme len tie vyznamnejsie
		{ 
            printf("Medzera %d: %lld krat\n", g, globalna_statistika[g]);
        }
    }

    return 0;
}
