optymalizowanie algorytmu

0

algorytm ma za zadanie obliczyć sumę wszystkich liczb pierwszych < 2000000, napisałem takie coś w c#, działa ale wykonuje sie kilka minut.. można to jakoś zoptymalizować? czy trzeba całość od nowa (poprawnie)?

         static void Main(string[] args)
        {
            long suma = 0;
            for (int liczba = 2; liczba < 2000000; liczba++)
            {
                if (jestPierwsza(liczba))
                {
                    suma += liczba;
                }
            }
            Console.WriteLine(suma);
            Console.Read();
        }

        static bool jestPierwsza(int liczba)
        {
            for (int i = 2; i < liczba; i++)
            {
                if (liczba % i == 0) {
                    return false;
                }
            }
            return true;
        }
0

Szybki hint na przyspieszenie 2 razy?

  • z liczb parzystych tylko 2 jest liczbą pierwszą, więc jaki sens sprawdzać wszystkie?
    Kolejny hint?
  • z liczb podzielnych przez 3 tylko 3 jest liczbą pierwszą, więc jaki sens sprawdzać wszystkie?

O szukaniu licz pierwszych już sporo zostało napisane, poszukaj...

0

Użyj Sita Eratostenesa do przesiania liczb, a następnie je zsumuj.

0

jeszcze jeden hint
nie trzeba sprawdzać, czy x dzieli się przez jakąkolwiek liczbę z zakresu 2 do x-1 - wystarczy sprawdzić, czy dzieli się przez liczby pierwsze z zakresu 2 do x-1 a tych jest znacznie mniej i masz je już obliczone w poprzednich krokach

0

Gdyby podpowiedź @Misiekd była zbyt trudna w implemetnacji to nie trzeba sprawdzać wszystkich liczb aż do N, wystarczy sprawdzać do pierwiastka z N (bo potem zaczną ci się pary powtarzać...)

1 użytkowników online, w tym zalogowanych: 0, gości: 1