Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++ ] SPOJ Prime_T, problem z algorytmem czy jego zapisem?

Ostatnio zmodyfikowano 2015-12-02 06:56
Autor Wiadomość
kakamxx
Temat założony przez niniejszego użytkownika
[C++ ] SPOJ Prime_T, problem z algorytmem czy jego zapisem?
» 2015-12-01 21:27:32
Treść zadania:

Sprawdź, które spośród danych liczb są liczbami pierwszymi:

                              Input
n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000]
                            

                              Output
Dla każdej liczby słowo TAK, jeśli liczba ta jest pierwsza, słowo: NIE, w przeciwnym wypadku.


Mój kod:
C/C++
#include <iostream>
using namespace std;

int main()
{
   
    for( int i = 1; i < 10; i++ )
    {
        for( int p = 2; p < 10; p++ )
        {
            if( p == i )
                 cout << "TAK" << endl;
           
            else if( i % p == 0 )
                 cout << "NIE" << endl;
           
        }
    }
   
   
    system( "PAUSE" );
    return 0;
}

Mogę prosić o sugestię co w moim rozumowaniu jest złe?
P-141247
ArgonZapan
» 2015-12-01 22:40:35
Nie za bardzo rozumiem treść twojego zadania, ale co do algorytmu ...
Liczba pierwsza, to taka, która jest podzielna przez 1 i przez samą siebie. Więc warunek (i == p) jest trochę dziwny.
Załóżmy, że i = 6 i p = 6
Wtedy wypisze "TAK"
ale czy 6 jest podzielne tylko przez 1 i 6 ? Hm....
P-141256
kakamxx
Temat założony przez niniejszego użytkownika
» 2015-12-01 23:02:30
Chodzi o to, że program ma sprawdzać po kolei liczby z przedziału [1 ... n] i wypisywać "TAK" jeśli dana liczba jest pierwsza, a "NIE" jest nie jest. OK, przeanalizowałem sobie to co tam wyskrobałem i doszedłem do wniosku, że to nie ma sensu. Wiem,że da się to zrobić za pomocą sita Eratostenesa, natomiast jestem cały czas na etapie pętli, do tablic jeszcze nie doszedłem. Pytanie - da się to zrobić za pomocą samych pętli? Wiem, że liczba n jest pierwsza gdy jest podzielna tylko przez 1 i samą siebie, natomiast nie mam pojęcia jak napisać taki warunek.
P-141262
ArgonZapan
» 2015-12-01 23:28:35
Da się zrobić na samych pętlach.
Powiedzmy, że chcesz sprawdzić czy N jest liczbą pierwszą
to musisz sprawdzić przypadki, czy jest podzielna przez 2,3,4,5,6,7,8,9,10... N-1 (Czyli tutaj masz pętle (int i = 2, i < N; i++)
jeśli N będzie podzielne przez jakąkolwiek liczbę z tego przedziału, oznacza że nie jest liczbą pierwszą.
Więc w tej pętli musisz mieć jakiegoś if'a który to sprawdzi i dodatkową zmienną która zapamięta wynik po wyjściu z pętli
Jak już wyjdziesz z pętli to po prostu sprawdza czy dana zmienna oznacza prawdę lub fałsz i na tej podstawie wypisze tak lub nie

Ale lepiej będzie chyba, jak odpuścisz sobie na razie tego SPOJ'a i pouczysz się np z kursów na tej stronie, lub z jakiejś książki i poprzerabiasz zadania domowe, które bd na twoim poziomie nauki. Bo znając same pętle ciężko cokolwiek zdziałać :)
P-141265
mateczek
» 2015-12-02 06:56:39
chyba Ci się algorytmy pomyliły !!! to co wkleiłeś niema dokładnie nic wspólnego z zadaniem
C/C++
int main() {
    int liczbaTestow, liczba;
    cin >> liczbaTestow; // na początek pobierasz liczbę testow
    while( liczbaTestow-- ) {
        cin >> liczba; //wczytujesz liczbę
        bool pierwsza = sprawdCzyPierwsza( liczba ); // sprawdzasz czy liczba jest pierwsza - musisz funkcje napisac :P
        if( pierwsza ) cout << "TAK" << endl; else cout << "NIE" << endl;
    }
}

czy jest podzielna przez 2,3,4,5,6,7,8,9,10... N-1
sprawdzasz maksymalnie do max=sqrt(N)- pirewiastek. Jeśli liczba będzie 36 ostatnią liczbą testową powinno być 6!!! inaczej będzie przekroczenie czasu !!!

Nie za bardzo rozumiem treść twojego zadania

spoi to taki fajny automat testujący programy !!! masz napisać kod, który zostaje skompilowany na serwerze i zostaną dostarczone na wejście programu przykładowe dane testowe - tutaj w maxymalnej liczbie 100tys testów.
P-141271
« 1 »
  Strona 1 z 1