usprawnienie programu w c

[s3ba]

Zadanie:
2. Napisać funkcję czyPierwsza sprawdzającą czy dana liczba jest liczbą pierwszą; przy jej
pomocy:
a) wypisać pierwszą setkę liczb pierwszych o wartości powyżej 10^9 ,
b) wygenerować 10000 liczb losowych i wyznaczyć częstość występowania liczb
pierwszych.

Napisalem taki kod, oblicza chyba poprawnie, jednak program jest strasznie wolny, czy ktos ma pomysl jak go usprawnic aby chodzil szybciej? Chodzi o podpunkt a). Z gory dzieki za pomoc.

Kod: Zaznacz cały

#include <stdio.h>

int pierwsza( int liczba )
{
    int czy_pierwsza = 1, x = 2;

    while( ( x <= ( liczba / 2 )) && ( czy_pierwsza == 1 ) )
            {
             if( liczba % x == 0 )
             czy_pierwsza = 0;
             ++x;
             }
             return czy_pierwsza;
}
int main(){
    	int liczba=pow(10,9),x=0;

        for (liczba; liczba <= pow(10,12); liczba++)
        {
        if( pierwsza( liczba ) == 1 )
        {	printf( "Liczba %d jest liczba pierwsza.
", liczba );
        	x++;
            }
        if (x==100)
        break;
        }
        
        system("pause");
}

[spajder]

Dla tak dużych liczb niestety nie ma sensu pisać Sita Eratostenesa. Do do usprawnień:
1. nie trzeba dzielić przez wszystkie liczby do \(\displaystyle{ \frac{n}{2}}\), wystarczy do \(\displaystyle{ \sqrt{n}}\)

2. Jeśli chcesz naprawdę usprawnić program to musisz zupełnie zmienić test pierwszości. Jest dużo metod, poczytaj sobie: