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

wydajność programu

Object Storage Arubacloud
0 głosów
239 wizyt
pytanie zadane 24 lutego 2022 w C i C++ przez jagfoljersolen Początkujący (250 p.)

Jak usprawnić ten program, aby działał szybciej? Napisałam go na spoj ale niestety przekracza limit czasu.

#include <iostream>

using namespace std;

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

}

int main()
{
    int n,number;

    cin>>n;

    while(n>=1 && n<=100000){

    for(int i=0; i<n;++i){
        cin>>number;
   if(czy_pierwsza(number)){
       cout<<"TAK"<<endl;
   }else{
       cout<<"NIE"<<endl;
   }
        }
    }
}

 

1 odpowiedź

+1 głos
odpowiedź 24 lutego 2022 przez Whistleroosh Maniak (56,980 p.)
Żeby sprawdzić czy liczba x jest pierwsza wystarczy sprawdzić czy jest podzielna przez dowolną liczbę od 2 do sqrt(x)
1
komentarz 24 lutego 2022 przez edutomek Dyskutant (8,380 p.)
No to standardowo: nie jestem matematykiem, ale się wypowiem ;-)

Pierwsza sprawa: jeśli liczba nie jest podzielna przez 2, to nie jest również podzielna przez: 4, 6, 8, 10, ... itd.

Analogicznie dla podzielności przez 3, 5, 7, 11 itd.. (Swoją drogą polecam się chwilę zastanowić, jeśli ktoś nie wie, dlaczego wymieniłem akurat takie liczby, pomijając np. liczbę 9. Radzę również poczytać o tzw. sicie Erastotenesa.)

Zastosowanie tej wiedzy skomplikuje algorytm, ale powinno również pozwolić na przyspieszenie obliczeń.

Druga sprawa: to nieco bardziej zaawansowany temat, ale jak ktoś się nie boi algebry modulo, to warto zapoznać się z testem Fermata (oraz innymi tego typu). Nie jest to stuprocentowo pewny test; mówi się nawet o liczbach "prawdopodobnie pierwszych", ale AFAIK w kryptografii jest wykorzystywany. Kto wie, może na SPOJu też się przyda?

Gdyby ktoś zechciał iść tym tropem, to zwrócę tylko uwagę na to, że tam jest mowa o działaniach w algebrze modulo: czyli mamy np. potęgowanie (w modulo). Warto również zaimplementować algorytm szybkiego potęgowania.

Podobne pytania

0 głosów
0 odpowiedzi 336 wizyt
pytanie zadane 14 grudnia 2021 w Sprzęt komputerowy przez TulismanoreV Nowicjusz (120 p.)
0 głosów
1 odpowiedź 537 wizyt
pytanie zadane 2 listopada 2021 w C i C++ przez xsw21qaz Nowicjusz (120 p.)

92,757 zapytań

141,679 odpowiedzi

320,438 komentarzy

62,101 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

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!

...