PRIME_T - Liczby Pierwsze

[pawoj20]

Co powinno zatem wyświetlić się w przypadku 1?

Powinno wyswietlic sie “NIE”. Na przyklad:

  if ( liczba == 1)
    {
        cout << "NIE"<<endl;
        continue;
    }

Podejrzewam, że ta konstrukcja jest nieprawidłowa, chociaż nie mogę znaleźć konkretnego przypadku dla którego będzie źle.

Znalazlem w miare duza liczbe- 7727 jest liczba pierwsza. Program zwraca “NIE”, wiec konstrukcja jest zla. Mozna zrobic instrukcje warunkowa sprawdzajaca reszte z dzielenia, a nie mnozyc.

Praca domowa dla chętnych, przy jakiej najmniejszej liczbie pierwszej nastąpi przepełnienie INT.?

Przepelnienie int powinno nastapic dla 13! (bo rzeczywiscie w zmiennej spr liczona jest jakby silnia). Ale konstrukcja jest jak widac madrzejsza ode mnie (na pewno dobrze rozpoznaje liczby pierwsze do 1000- zabraklo mi cierpliwosci zeby przekleic wynik dla 10000 wartosci z ideone)

[narbej]

Przepelnienie int powinno nastapic dla 13! (bo rzeczywiscie w zmiennej spr liczona jest jakby silnia). Ale konstrukcja jest jak widac madrzejsza ode mnie

TZn To było tylko takie skojarzenie na szybko. Dokładnie spr jest iloczynem reszt z dzielenia a te reszty, dla liczby pierwszej są różne od zera i dla dużej liczby pierwszej mogą być coraz większe np
x %2 = 1
x %3 = [1,2]
x%4 = [1,2,3]
x%5 = [1,2,3,4]
…
x%100 = [1…99]
dla x >= 10000

Dodatkowo nie jestem pewny, czy każde przepełnienie, spowoduje wyzerowanie zmiennej spr.

[dodename_1]

Jak rozumiem Panowie, owo przepełnienie sprawia, że zmienna spr po osiągnięciu odpowiednio dużej wielkości zeruje się, ponieważ nie ma w niej miejsca tak? W takim wypadku wystarczy, żebym wykonał taką instrukcję:

long long int spr = 1;

I wówczas miejsca jest wystarczająco. Ostatnią liczbą pierwszą przed 10 000 jest 9973 i ta liczba jest wskazywana przez program jako pierwsza (przetestowałem to). Mimo to, sędzia wciąż odrzuca odpowiedzi. Dlaczego?

EDYCJA:

Ok, był błąd dla jedynki (wyskakiwały dwa komunikaty), ale udało mi się go zażegnać. Mimo tego, sędzia wciąż wskazuje błąd. Wklejam cały program, ponieważ przeszedł pewne zmiany, a już skończyły mi się pomysły, gdzie jest coś nie tak:

#include
#include <math.h>

using namespace std;

int main()
{
int i, dzielnik, liczba,j;
int pierw;
long long int spr = 1;
cin >> j;

for (int k=0; k < j; k++)
{
cin >> liczba;

pierw = sqrt(liczba);

for (i = 2; i <= pierw; i++)
{
    dzielnik = liczba % i;
    spr = spr*dzielnik;

}

if (spr == 1 && liczba ==1)
{
    cout << "NIE" << endl;

}

if (spr == 0)
{
    cout << "NIE" << endl;

}
if ((spr != 0 && liczba!=1) || liczba == 2)
{
    cout << "TAK" << endl;
}
spr = 1;
}

return 0;

}

[hipcia]

Jak widzę tak wstawiony kod to moja chęć pomocy spada o 99%. Typ long long int jest za mały. Nie szukaj dalej. Nie ma sensu wykonywać działań po przepełnieniu inta.

[dodename_1]

W takim razie nie pomagaj, skoro aż tak Cię to razi. Wklejam na Ideone, tak jak mi zalecono i daję kopiuj. Takie coś otrzymuję.

Jeżeli jest za mały, dlaczego program wypluwa poprawne wyniki?

[narbej]

Jak widzę tak wstawiony kod to moja chęć pomocy spada o 99%. Typ long long int jest za mały. Nie szukaj dalej. Nie ma sensu wykonywać działań po przepełnieniu inta.

Prawie się zgadzam z @hipcia w całej rozciągłości i w prawie 100%, ale u mnie niechęć sięga 99,9%. Nigdy jeszcze nie widziałem takiego podejścia do tego zadania, więc może to dobrze? Jeżeli nie int i nie long long to zostają jeszcze do przetestowania float, double i long double. Tak naprawdę to wystarcza tu typ bool, ale jak nie wiesz jak to zrobić …

Mimo wszystko gratuluję samodzielności [z małą pomocą forum]. I moje rady:
Naucz się poprawnie wklejać kod lub korzystaj z ideone.com !!! No i może przeczytaj w końcu: Jeśli zaczynasz, przeczytaj koniecznie! <-- to jest link,w który musisz kliknąć.

[hipcia]

Nie wypluwa poprawnych wyników:

INPUT:

1
9587

OUTPUT:

TAK

[hipcia]

@narbej Faktycznie zmiana na double to znakomity pomysł Program zostanie zaliczony chociaż metoda mogłaby być szybsza z boolem.

[narbej]

zmiana na double to znakomity pomysł Program zostanie zaliczony chociaż

Cóż, powiem nieskromnie, że wiem

Tzn, wiem, że zostanie zaliczony. Po prostu pisząc że zostały do przetestowania, równolegle przetestowałem te opcje w tym samym czasie [no może odrobinkę wcześniej], bo inaczej bym o nich nawet nie wspominał.
Bo pomysł nie jest znakomity, to tylko taka tam proteza czy obejście, wybrnięcie z problemu. Rozwiązań jest tu multum prostszych, ale okazuje się, że jest też i taki jak wyżej sposób i @dodename_1 będzie mógł się cieszyć kolejnym AC.

[dodename_1]

Hej! Rzeczywiście zmiana na double zadziałała!

Co do innych rozwiązań - to też podsunął mi kolega, ja miałem nieco inne, ale to mi się bardzo spodobało. Trwałem przy programie, ponieważ nie znam rozwiązań ze zmienną “bool”, a nie chciałem bezmyślnie kopiować innych schematów, tylko oprzeć się na szkielecie programu, do którego udało mi się samemu dotrzeć i poszukać pomocy u innych, bardziej doświadczonych użytkowników w tych miejscach, których nie rozumiałem.

Wszystkim bardzo dziękuję za pomoc!

[korkirw]

Gratulacje zaliczenia zadania, jednak myślę, że warto byś jednak spróbował rozwiązania z typem bool.
Zresztą nie musi to być typ bool, wystarczy typ int.
Podpowiedź:
int p = 0;
…
for(){
…
if(coś tutaj)
p=1;
}
if(p )
…
else
…
p=0;
To jest oczywiście tylko szkielet

Metoda z typem double chociaż tutaj przeszła, jest moim zdaniem takim rozwiązaniem zastępczym. Poza tym wydaje mi się, że mogłaby już niedobrze pracować dla większych liczb np. dla liczb bliskich 1000 000 000 podejrzewam, że będzie wykazywać, że nie ma tam liczb pierwszych.

[ospek_94]

Hej, czy mógłby ktoś zerknąć na kod i podpowiedzieć co mógłbym poprawić aby został zatwierdzony. Generalnie wydaje mi się, że wszystko działa jak powinno ale jak widać coś jest jednak nie tak

 int n = int.Parse(Console.ReadLine());
        if (n < 100000)
        {
            for (int j = 0; j < n; j++)
            {
                int a = int.Parse(Console.ReadLine());
                if (a > 0 && a <= 10000)
                {
                    for (int i = 0; i < 1; i++)
                    {
                        if ( a == 1 || a % 2 == 0 && a != 2 || a % 3 == 0 && a != 3) 
                        {
                            Console.WriteLine("NIE");
                        }
                        else
                        {
                            Console.WriteLine("TAK");
                        }
                    }
                }
            }
            Console.ReadKey();
        }

[korkirw]

Wszystko działa jak należy? To pochwal się ile i jakie przypadki sprawdziłeś, najlepiej przez link do ideone. Np. co wychodzi Ci dla 25…

[ospek_94]

Wpisywałem randomowe liczby. Dla 25 faktycznie wychodzi zły wynik. Czyli jeszcze muszę popracować nad :
if ( a == 1 || a % 2 == 0 && a != 2 || a % 3 == 0 && a != 3)

[pawoj20]

Jest 25 liczb pierwszych, ktore sa mniejsze od 100.
Jesli uda sie zrobic w analogiczny sposob powyzszy warunek to bedzie wygladal imponujaco.

[mortalrave]

Hej, sędzia pokazuje mi, że ten kod przerkacza limit czasu. Ma ktoś pomysł dlaczego tak jest? Kod w Pythonie

n = input()
j = 0
k=[]
for n in range(0,int(n)):
    i=0
    number = input()
    for nu in range(2,100000):
        if int(number) % nu == 0:
            i+=1
    if i != 1:
        k.append("NIE")
    else:
        k.append("TAK")
for num in k:
    print(num)

[pawoj20]

1. Jeśli zaczynasz, przeczytaj koniecznie! <--kliknij w to proszę!

2. czy jest sens sprawdzac dzielniki, ktore sa co najmniej 10 razy wieksze niz sprawdzana liczba.

3. czy jest sens sprawdzac dzielniki wieksze niz sprawdzana liczba.

4. Brute force w pythonie na tym zadaniu moze sie nie udac

[mortalrave]

Sito Eratostenesa pomogło. Dziękuję za pomoc.

[jarekish]

Hej, ciekawi mnie czemu zamiast zwykłego print(“TAK”) albo print(“NIE”) w if i != 1: ; else: dodajesz do listy i potem pętlą drukujesz listę?

Pytam bo dopiero uczę się Pythona i zwyczajnie nie rozumiem czy np. są z tego jakieś korzyści.

[mortalrave]

Program zrobi to samo ale nie wyświetli tego w wymagany sposób. Wyjdzie Ci np:
3
TAK
4
NIE
5
TAK