Algorytm sprawdzania czy liczba jest pierwsza

pytanie zadane 11 maja 2019 w Matematyka, fizyka, logika przez Paweł Puchowicz Nowicjusz (140 p.)

Hej, pisze prosty program, który sprawdzą czy podana liczba jest pierwsza i przy tym zlicza liczbę dzieleń wykonywaną przez algorytm żeby dojść do końcowego wyniku.

W swoim programie wykorzystywałem 2 algorytmy. Pierwszy - niezbyt optymalny, przez co czas oczekiwania na wynik znacznie się wydłuża, drugi - lepszy, natomiast nie mam pomysłu w jaki sposób jeszcze mógłbym go usprawnić żeby jeszcze bardziej zmniejszyć liczbę dzieleń.

W tym miejscu zwracam się z prośbą o pomoc do Was, czy może macie jakieś pomysły?

Z góry dzięki! Niżej kod do obu algorytmów napisany w c#.

if (PunktPomiarowy < 2) return false;
            else if (PunktPomiarowy < 4) return true;
            else if (PunktPomiarowy % 2 == 0) return false;
            else for (BigInteger u = 3; u < PunktPomiarowy / 2; u += 2)
                {
                    if (PunktPomiarowy % u == 0) return false;
                    
                }

         if (PunktPomiarowy < 2) return false;
            for (BigInteger i = 2; i*i<=PunktPomiarowy;i++)
            {
                if (PunktPomiarowy % i == 0) return false;
                
            }

komentarz 12 maja 2019 przez niezalogowany

może wykluczyć dzielenie przez wielokrotność 5

if (PunktPomiarowy < 2) return false;
            else if (PunktPomiarowy < 4) return true;
            else if (PunktPomiarowy % 2 == 0) return false;
            else for (BigInteger u = 3; u < PunktPomiarowy / 2; u += 2)
                {	// xxx3
                    if (PunktPomiarowy % u == 0) return false;
			u+=4; // xxx7
		    if (PunktPomiarowy % u == 0) return false;
			u+=2; // xxx9
		    if (PunktPomiarowy % u == 0) return false;
			u+=2; // xxx1
		    if (PunktPomiarowy % u == 0) return false;
                    
                }