• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

SPOJ Liczby Pierwsze

VPS Starter Arubacloud
0 głosów
502 wizyt
pytanie zadane 18 września 2020 w C i C++ przez patrykos125 Nowicjusz (170 p.)

Witam .Wczoraj rozpocząłem swoją przygodę z Spojem i natrafiłem na zadanie pod tytułem Liczby pierwsze .

Wydaje mi się że mój program działa poprawnie ale sędzia mi go nie przepuszcza może wam  uda się znaleźć błąd.

Z góry dzięki za pomoc.

#include <iostream>

using namespace std;


int main() {


    int n;
    int a;
    int licznik = 0;
    cin >> n;//liczba testów
    cin >> a;//liczba do sprawdzenia

    for (int i = 0; i < n; ++i) {


        for (int j = 2; j < a; ++j) {
            if (a % j == 0)licznik++;
            if (licznik > 0)break;

        }
        if (a == 1 || a == 0 || licznik > 0) { cout << "NIE"; }
        else { cout << "TAK"; }
        licznik = 0;
        cin >> a;

    }


    return 0;
}

 

2 odpowiedzi

0 głosów
odpowiedź 18 września 2020 przez profesorek96 Szeryf (91,420 p.)
wybrane 19 września 2020 przez patrykos125
 
Najlepsza

Sędzia ci go nie przepuszcza ponieważ może w pewnych przypadkach brzegowych dawać nie poprawne wynik lub jest za wolny. Wszystkie sprawdzaczki działają na podobnej zasadzie. Twórca zadania tworzy testy. Każdy z testów składa się z danych wejściowych oraz oczekiwanego wyniku. Każdemu z testów można określić również czas w jakim program rozwiązujący dany problem na podstawie danych zawartym w teście zwraca wynik.

Wysyłając nasz kod, program jest kompilowany, następnie jest uruchamiany dla każdego z przypadków testowych. Sprawdzany jest czas w jakim został obliczony wynik oraz to czy nasz wynik zgadza się z poprawnym wynikiem dla danego testu.

W twoim rozwiązaniu problemem jest zapewne czas tak zwana złożoność obliczeniowa. Wyjaśnijmy sobie następującą kwestię, jeśli chciałbyś stwierdzić czy liczba jest pierwsza czy nie to wystarczy że znajdziesz co najmniej jeden dzielnik większy bądź równy dwa i mniejszy od niej samej. Pierwsze co przyjdzie ci do głowy to takie rozwiązanie:

bool czy_pierwsza(int n)
{
	if(n<=1)return false;
	for(int i=2;i<n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}

Sprawdzam przypadek brzegowy jeśli liczba nie jest 1 to wykonuje pętle for. Jeśli znajdę takie i które jest z przedziału od 2 do n-1 to nastąpi przedwczesne zakończenie pętli. Funkcja zwróci wartość false oznaczająca że podana liczba n nie jest pierwsza. Co jeśli liczba faktycznie jest pierwsza ?

Wtedy pętla for wykona cię n-2 razy. Dla małych liczb pierwszych nie ma to większego znaczenia jednak jeśli na warsztat weźmiemy liczbę 104723. Liczba ta jest liczbą pierwszą, aby to stwierdzić nasz program będzie musiał wykonać aż 104721 operacji. Jak pewnie zauważyłeś nie jest to zbyt optymalne prawda ;)

Naszym celem nie jest sprawdzenie i wyznaczenie wszystkich dzielników, wystarczy że znajdziemy choć jeden. Istnieje takie twierdzenie matematyczne że jeśli liczba ma dzielnik to ten dzielnik jest mniejszy bądź równy pierwiastkowi kwadratowemu z tej liczby.

dzielnik<=sqrt(n)

Pewnie myślisz że wystarczy zamienić i<n na i<=sqrt(n) w warunku końca pętli for. Niestety nie jest to koniec. Komputer wykonuje bardzo dużo obliczeń by obliczyć pierwiastek kwadratowy z dowolnej liczby (Metoda Newtona). Obliczanie pierwiastka jest kosztowne, zysk jaki osiągnęliśmy w ten sposób przez algorytm sqrt został by zmarnotrawiony. Nie martw się wystarczy proste działanie, jakim jest podniesienie tej nierówności stronami do potęgi. Komputery bardzo szybko mnożą.

dzielnik<=sqrt(n) -> dzielnik*dzielnik<=n

Tym sposobem uzyskaliśmy finalny obraz naszej funkcji sprawdzającej czy podana liczba jest pierwsza.

bool czy_pierwsza(int n)
{
	if(n<=1)return false;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}

 

komentarz 19 września 2020 przez patrykos125 Nowicjusz (170 p.)
Bardzo ci dziękuje za tak wyczerpującą odpowiedz .Twoja odpowiedz mi uzmysłowiła jak bardzo mało wiem o programowaniu i o liczbach pierwszych
komentarz 19 września 2020 przez profesorek96 Szeryf (91,420 p.)
Proszę bardzo :)

Polecam sobie zakupić kilka książek i je dokładnie przestudiować.

Zacznij od książki D.Harela Rzecz o istocie informatyki. Algorytmika

Polecam również książkę Piramidy szyszki i inne konstrukcie algorytmiczne autorstwa M. Sysło
komentarz 19 września 2020 przez patrykos125 Nowicjusz (170 p.)
Kupiłem 3 tomy Opus Magnum Grębosza ale powiem szczerze że jeszcze się za nie nie zabrałem .Mam kolejne pytanie  do zadania ze spoja   mogę tutaj przedstawić mój problem ?
komentarz 19 września 2020 przez profesorek96 Szeryf (91,420 p.)
To polecam się wziąść za studiowanie Opus jak i tych książek. Zasadniczo nowy problem nowy temat. Jeśli jednak dotyczy to tego zadania to słucham.
komentarz 19 września 2020 przez patrykos125 Nowicjusz (170 p.)

Nie tyczy to się zasadniczego tego samego  zadania ale bardziej o sposób pisania kodu pod spoj .Pytanie tyczy   się zadania o tytule "DOUGHNUT - Harry and big doughnuts"

z pozoru banalne ale nie wiem co robię nie tak i dlaczego mi tego nie uznaje ?

#include <iostream>

using namespace std;



int main(){
    int unsigned t;
    int c,k,w;
    cin>>t;
    for (int i = 0; i <t ; ++i) {
        cin>>c>>k>>w;
        if(w*c>k)cout<<"no";
        else cout<<"yes";


    }
    return 0;
}

 

komentarz 19 września 2020 przez patrykos125 Nowicjusz (170 p.)
Udało mi samemu rozwiązać problem wystarczyło wstawić <<endl; na końcu textu
1
komentarz 19 września 2020 przez patrykos125 Nowicjusz (170 p.)

@profesorek96,
 Sprawdzałem czas wykonywania kodu na spoju mój pierwotny kod wykonywał się w 0.38 natomiast poprawiony przy pomocy twoich rad w 0.21

0 głosów
odpowiedź 18 września 2020 przez TOM_CPP Pasjonat (22,640 p.)

Twój algorytm ma złożoność obliczeniową rzędu O(n), a powinien mieć O(sqrt(n))

Zobacz taki przykład:

bool isPrime( long long int n )
{
  if( n <= 1 ) return false;
  int i {2};
  while( i*i <= n ) if( n%i++ == 0 ) return false;

  return true;
}

 

komentarz 18 września 2020 przez patrykos125 Nowicjusz (170 p.)
Dzięki za szybką odpowiedz ale nie rozumiem jak to ma działać
komentarz 18 września 2020 przez TOM_CPP Pasjonat (22,640 p.)

To jest funkcja sprawdzająca czy dana liczba jest pierwsza, którą można wywołać w main(). np.

int main()
{
  int n {0};
  cin >> n;
  cout << ( isPrime(n) ? "TAK" : "NIE" );
}

W funkcji isPrime(...) wykorzystywana jest pętla while w której nie sprawdza się po kolei każdej wartości (jak to jest w Twoim przypadku i stąd ta złożoność liniowa ), ale wartości sprawdzane są co pewną "odległość", która rośnie w postępie kwadratowym (i*i) .

komentarz 18 września 2020 przez patrykos125 Nowicjusz (170 p.)
Teraz rozumiem dzięki za odpowiedz ale sam bym w życiu na takie rozwiązanie nie wpadł. Nie wiedziałem ze spoj sprawdza kod pod względem optymalizacji i szukałem sporą ilość czasu błędu w kodzie

Podobne pytania

0 głosów
0 odpowiedzi 189 wizyt
pytanie zadane 1 sierpnia 2023 w C i C++ przez Jakub005 Początkujący (310 p.)
0 głosów
1 odpowiedź 381 wizyt
0 głosów
0 odpowiedzi 369 wizyt
pytanie zadane 2 stycznia 2020 w SPOJ przez Bezk Nowicjusz (140 p.)

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...