optymalizowanie algorytmu

Odpowiedz Nowy wątek
2011-07-22 10:52
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;
        }
edytowany 1x, ostatnio: Markness, 2011-07-22 10:52

Pozostało 580 znaków

2011-07-22 11:00
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...

Pozostało 580 znaków

2011-07-22 12:26
0

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

Pozostało 580 znaków

2011-07-22 12:34
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


- Ciemna druga strona jest.
- Nie marudź Yoda, tylko jedz tego tosta.
Google NIE GRYZIE!
Pomogłem - kliknij

Pozostało 580 znaków

2011-07-22 12:48
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ć...)

ok panowie dzięki wielkie za podpowiedzi! - Markness 2011-07-22 21:46

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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