SPOJ-Liczby Pierwsze :: 4programmers.net

PeterMeister

2016-05-30T20:19:48+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 5

0

Kopiuj

 
```
Mam problem z zadaniem Liczby Pierwsze na spoju. Robię już to zadanie któryś raz, cały czas wymyślam nowe rozwiązania, ale za każdym razem jest błąd, i nie mam pojęcia jaki. Oto mój kod:

Kopiuj

#include <iostream>
#include <cstdlib>

using namespace std;

int x;

int main()
{
    cin>>x;

    for(int i=2; i<=10000; i++)
    {
        if((x%i==0)&&(i!=x))
        {
            cout<<"NIE";
            break;
        }

        else if(x==1)
        {
            cout<<"TAK";
            break;
        }

        if(i==10000)
        {
            cout<<"TAK";
        }



    }


    return 0;
}

Liczę na pomoc i z góry dziękuję, oto link do zadania: http://pl.spoj.com/problems/PRIME_T/

pingwindyktator

2016-05-30T20:31:00+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Kraków
Postów: 1055

0

To jakiś żart?

PeterMeister

2016-05-30T20:33:03+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 5

0

Nie, jeśli wież gdzie jest błąd, to proszę o wytłumaczenie

Shalom

2016-05-30T20:39:23+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Space: the final frontier
Postów: 26433

2

Twój kod nie ma nic wspólnego z podanym zadaniem. Przecież nie zadziała nawet dla przykładowych danych. Błąd jest taki że nie masz pojęcia co robisz. I to nie jest problem programistyczny, tylko matematyczny. Weź łaskawie do ręki kartkę papieru i prześledź co twój algorytm robi dla podanych w zadaniu przykładowych danych...

PeterMeister

2016-05-30T20:57:41+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 5

0

Kopiuj

cin>>x;

prosi o podanie "x"

Kopiuj

for(int i=2; i<=10000; i++)

powtarza instrukcje od "i" równego 2 do i mniejszego lub równego 10000 i co wykonanie się tych instrukcji zwiększa i o jeden

Kopiuj

if((x%i==0)&&(i!=x))
        {
            cout<<"NIE";
            break;
        }

jeśli reszta z dzielenia "x"/i" jest równa 0 i równocześnie "i" jest różne niż "x" to wyświetla NIE i łamie pętle

(bo wszystkie liczby które dzielą się tylko przez 1 i przez samą siebie są liczbami pierwszymi, czyli to wykluczy liczby które nimi nie są)

Kopiuj

else if(x==1)
        {
            cout<<"TAK";
            break;
        }

jeśli nie, to sprawdza czy "x" jest równe 1
gdy tak się stanie wyświetla TAK i łamie pętle

(bo 1 też jest liczbą pierwszą)

Kopiuj

if(i==10000)
        {
            cout<<"TAK";
        }

potem poza pętlą jeśli "i" będzie równe 10000, to wyświetla TAK

(bo wszystkie inne liczby, to są liczby pierwsze)

pingwindyktator

2016-05-30T21:02:10+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Kraków
Postów: 1055

3

bo 1 też jest liczbą pierwszą

co

PeterMeister

2016-05-30T21:08:53+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 5

0

Myślałem, że jest bo jest podzielna przez 1 i przez samą siebie, ale teraz sprawdziłem i wiem, że nie, przepraszam

sig

2016-05-30T21:10:27+02:00

Rejestracja: dni
Ostatnio: dni

0

Liczba nie może mieć dzielników większych od niej, w zasadzie starczy sprawdzić do jej pierwiastka włącznie. Dodatkowo twój program sprawdza tylko czy ilość liczb do sprawdzenia jest liczbą pierwszą (czyli jedyną liczbę na wejściu której nie powinien sprawdzać). Weźmy przykład spod zadania,jest tam:
3
11
1
4
Czyli 3 liczby do sprawdzenia: 11, 1, 4. Twój program sprawdza liczbę 3 zamiast tych trzech liczb co powinien.

Shalom

2016-05-30T21:13:37+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Space: the final frontier
Postów: 26433

0

@PeterMeister brawo, a teraz czytamy treść zadania:

Podają liczbę testów N, u ciebie tego nie ma...
Dla każdego testu podają liczbę X i sprawdzamy jej pierwszość. Sprawdzanie dzielnika powyżej pierwiastka z X nie ma oczywiście sensu, ale to tego musiałbyś znać matematykę na poziomie szkoły podstawowej.
Nawet w treści zadania masz przyklad mówiący że 1 nie jest liczbą pierwszą...

kq

2016-05-30T21:14:49+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Szczecin

1

Tutaj masz kod, który wykonuje się u mnie w 0.35s: http://melpon.org/wandbox/permlink/veV971QB5k8dx0RI :D

Tak bardziej serio: zacznij od napisania funkcji isPrime przyjmującej int i zwracającą bool.

PeterMeister

2016-05-30T21:52:08+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 5

0

Teraz działa

Kopiuj

#include <iostream>
#include <cstdlib>

using namespace std;

int x,n;

int main()
{
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>x;

        for(int i=2; i<=10000; i++)
        {
            if((x%i==0)&&(i!=x))
            {
                cout<<"NIE"<<endl;
                break;
            }

            else if(x==1)
            {
                cout<<"NIE"<<endl;
                break;
            }

            if(i==10000)
            {
                cout<<"TAK"<<endl;
            }
        }
    }

    return 0;
}

Dzięki za pomoc :)

sig

2016-05-30T23:14:10+02:00

Rejestracja: dni
Ostatnio: dni

2

To ja dam kod co zalicza je w 0.01s

Kopiuj

 
//#include <iostream>
#include <stdio.h>
#include<math.h>
#include <stdbool.h>

//using namespace std;

bool czypierwsza(int liczba);

bool sprawdz[10001];

bool czypierwsza(int liczba)
{
    //if (liczba < 2) return false;
    int tab[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    int pierw = ceil(sqrt(liczba));
    int *licznik = tab;
    while (*licznik <= pierw)
    {
        if (liczba % (*licznik) == 0) return false;
        licznik++;
    }
    return true;
}

int main()
{
    bool *wsk = sprawdz;
    wsk += 4;
    for (int i = 4; i <=10000; i+= 2)
    {
        //sprawdz[i] = false;
        *wsk = false;
        wsk += 2;
    }
    wsk = sprawdz;
    wsk += 9;
    for (int i = 9; i <=10000; i+= 2)
    {
        //sprawdz[i] = czypierwsza(i);
        *wsk = czypierwsza(i);
        wsk += 2;
    }
    sprawdz[0] = false;
    sprawdz[1] = false;
    sprawdz[2] = true;
    sprawdz[3] = true;
    sprawdz[5] = true;
    sprawdz[7] = true;
    int ileserii = 0;
    scanf("%d", &ileserii);
    //cin >> ileserii;
    while (ileserii--)
    {
        int liczba = 0;
        //cin >> liczba;
        scanf("%d", &liczba);
        puts(sprawdz[liczba] ? "TAK" : "NIE");
        //if (sprawdz[liczba] == true) puts("TAK");
        //else puts("NIE");
    }

}

edit: aktualizacja kodu

spartanPAGE

2016-06-01T13:34:34+02:00

Rejestracja: dni
Ostatnio: dni

1

@sig masz, bo się zamęczysz :P
http://ideone.com/W4da7E