Projekt Euler - Problem numer 1

Projekt Euler (http://projecteuler.net) to strona internetowa zawierająca pokaźny zbiór (ponad 300) problemów obliczeniowych, do rozwiązania których potrzebny jest (w większości przypadków) komputer oraz dowolny język programowania. Rozwiązaniem każdego zadania jest wynik, który podajemy, aby sprawdzić czy nasz sposób obliczeń jest poprawny. Oczywiście sednem zabawy jest opracowanie odpowiedniego dla danego problemu algorytmu. Przyjrzyjmy się zatem pierwszemu zadaniu.

Weźmy wszystkie liczby naturalne mniejsze od 10, które są wielokrotnościami liczb 3 lub 5. Otrzymamy liczby: 3, 5, 6, 9. Ich suma wynosi 25. Znajdź sumę wielokrotności liczb 3 lub 5 mniejszych od 1000.

Najprostszy z możliwych algorytm powinien sprawdzić wszystkie liczby z podanego zakresu oraz zsumować tylko te, które są wielokrotnościami liczb 3 lub 5.

/**
 * Projekt Euler - Problem nr 1
 * @author kodatnik.blogspot.com
 */
public class PEProblem1 {
 public static void main(String args[]) {
  // zmienna przechowująca sumę
  int suma = 0;
 
  // pętla dla liczb naturalnych mniejszych od 1000 (zaczynamy od 3)
  for(int i = 3; i < 1000; i++)
   // jeśli liczba jest podzielna przez 3 lub 5 dodajemy ją do sumy
   if((i % 3 == 0) || (i % 5 == 0))
    suma += i;
         
  //wyświetlamy wynik
  System.out.println("Suma wynosi: " + suma);
 }
}

Otrzymany wynik to:

Suma wynosi: 233168

Pozostaje kwestia optymalizacji algorytmu. Czy można prościej, szybciej? Oczywiście. Pytanie tylko czy dla górnego zakresu (1000) jest to opłacalne?

10 Komentarzy - Projekt Euler - Problem numer 1

Anonimowy pisze...: Witam,

Powyższe rozwiązanie można rozwiązać w minutę na kartce papieru (a nawet w pamięci). Wystarczy podstawowa znajomość ciągów arytmetycznych i 'zasady włączeń i wyłączeń'.

Jeśli ktoś zechce napisać to w javie może zrobić to tak:
===============================================
// zmienna przechowująca sumę
int suma = 0;
int liczba;
int najwiekszy;

//dla 3
liczba = (1000-1)/3;
najwiekszy = liczba*3;
suma += (3+najwiekszy)*liczba/2;

//dla 5
liczba = (1000 -1)/5;
najwiekszy = liczba*5;
suma += (5+najwiekszy)*liczba/2;

//dla 15
liczba = (1000 -1)/15;
najwiekszy = liczba*15;
suma -= (15+najwiekszy)*liczba/2;
System.out.println("Suma to: " + suma);
===============================================

Zaletą tego rozwiązania jest oczywiście złożoność obliczeniowa.

Pozdrawiam,
Jacek Rutkowski; 8 października 2010 12:25
Devon pisze...: @Jacek: Jak najbardziej się z Tobą zgadzam, dlatego napisałem, że można prościej i szybciej :); 13 października 2010 23:30
Mateusz Cieślak pisze...: Całkowicie się zgadzam przy czym jak uważacie, czy drobna zmiana kosmetyczna może choć o ciut przyspieszyć algorytm:
zamiast używać konstrukcji:
liczba = (999)/3;
najwiekszy = liczba*3;

dać:
najwiekszy = 999 - 999%3

pozdrawiam,
Mateusz Cieślak; 24 marca 2011 17:35
DKnoto pisze...: 3 + 5 + 6 + 9 = 23 a nie 25

Mamy tu oczywiście dwa ciągi arytmetyczne:
c1 = 5 + 10 + 15 ...
c2 = 3 + 6 + 9 + ...
czyli dla liczb mniejszych od n = 10^p i p = 3 będzie to:
p = 3;
n = 10 ^ p;
s1 = ((5 + (n - 5)) * (n / 5 - 1)) / 2;
s2 = ((3 + (n - 1)) * (n-1) / 3) / 2;; 24 grudnia 2018 17:05
DKnoto pisze...: Wczoraj oczywiście zapomniałem jeszcze o jednym ciągu, którego sumę trzeba odjąć od (S1 + S2):-)

S3 = 15 + 30 + 45 + … + N - 10; 25 grudnia 2018 13:02
DKnoto pisze...: Ostateczenie po skróceniu otrzymujemy wzór:

Dla p <= 1, 2, 3, …
n = 10 ^ p

S = (7 * n^2 - 5 * n + 40) / 30;; 25 grudnia 2018 13:21
DKnoto pisze...: Ten komentarz został usunięty przez autora.; 25 grudnia 2018 14:03
DKnoto pisze...: Ten komentarz został usunięty przez autora.; 25 grudnia 2018 14:09
DKnoto pisze...: Co do pytania o opłacalność to liczenie sumy ze wzoru jest około 1 500 razy szybsze od algorytmu naiwnego.; 25 grudnia 2018 14:12
Anonimowy pisze...: super; 7 sierpnia 2023 18:38