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

wydajność programu

Aruba Cloud - Virtual Private Server VPS
0 głosów
267 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 (57,400 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 450 wizyt
pytanie zadane 14 grudnia 2021 w Sprzęt komputerowy przez TulismanoreV Nowicjusz (120 p.)
0 głosów
1 odpowiedź 759 wizyt
pytanie zadane 2 listopada 2021 w C i C++ przez xsw21qaz Nowicjusz (120 p.)

93,324 zapytań

142,323 odpowiedzi

322,390 komentarzy

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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...