Sito Eratostenesa i zadanie z nim związane.

Question

Siemka. Jestem uczniem klasy 1 tech. o profilu technik informatyk. Na poprzedniej lekcji PSIO otrzymałem 2 zadania. Pierwszym z nich było napisać program "Sito Eratostenesa". Drugie natomiast należy zrobić na podstawie tego programu a polecenie to: "Zadeklaruj tablice 100 elementową, wylosuj i wpisz do tej tablicy losowe liczby z zakresu 0-500. Sprawdź ile wśród nich jest liczb pierwszych." O ile za pierwszym zadaniem nie miałem problemu, to z drugim już nie potrafię sobie poradzić. W tym linku zamieszczam kod który zapisałem do pierwszego zadania : http://www.codeshare.io/bernard

Jeśli ktoś ma czas i chęci żeby pomóc będę bardzo wdzięczny :). Pozdrawiam

Answer 1

Ja sam robiłem podobne zadanie na SPOJu. Tylko program nie działa tak jak należy, bo wyświetla wartość "NIE" dla każdej liczby. Na razie nie mam czasu żeby w tym grzebać - dam Ci kod i jak chcesz, to sam pomyśl nad tym i możesz mi przy okazji wysłać poprawne rozwiązanie, bo od dłuższego czasu się z tym głowie. ^^

 

#include <iostream>

using namespace std;

const int n = 100;

bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);

int main()
{
    int liczba, test;
    cin >> test;

    while (test--)
    {
        cin >> liczba;

        for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie s¹ liczbami pierwszymi
        {
            if (numbersTable[i] == true) // je¿eli dana liczba jest ju¿ wykreœlona
                continue; // to przejdŸ do kolejnej
            for (int j = 2*i ; j <= n; j += i) // przejdŸ od liczby 2*i do n przesuwaj¹c siê o i
                numbersTable[j] = true; // i ka¿d¹ z nich usuwaj ze zbioru
        }

        for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
        {
            if (numbersTable[i] == false);// jeœli liczba nie zosta³a usuniêta ze zbioru

            if (i == liczba)
                cout << "TAK" << endl;

                else
                    cout << "NIE" << endl;
        }
    }
    return 0;
}

 

Comments

Dzięki za odp! Każda podpowiedź się przyda. Jeśli coś ogarne dam znać :).

Answer 2

Wystarczy przerobić pierwszy program, deklarujesz tablice 100-elementową zamiast n-elementową, potem pętlą wypełniasz tablicę losowymi liczbami (jeśli nie wiesz jak to zrobić: http://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Pseudolosowe-liczby-calkowite/290 albo https://www.youtube.com/watch?v=QapjTCGV7GM) i sprawdzasz je swoim algorytmem, czy są liczbami pierwszymi.

Comments

Gdy próbowałem zrobić tak jak radzisz natrafiłem na pewien problem. Jeśli zamiast n zadeklaruję tablice 100 elementową którą wypełnię losowymi liczbami z przedziału 0-500 w każdej komórce tablicy będą losowe liczby z wyżej zaznaczonego przedziału, zamiast true i false, więc automatycznie dalsza część kodu nie działa tak jak powinna. Będę podejmował dalsze próby z twoimi wskazówkami. Dodam tylko że dopiero raczkuje jeśli chodzi o programowanie w c++ i tego typu zadania, więc pewnie umknęło mi i w tym przypadku wiele rzeczy :). Dzięki za odp.

Answer 3

Witam, mam małe pytanie.

Otóż również jestem uczniem klasy 1 tech o profilu technik informatyk  jednak u mnie nie ma takiego przedmiotu jak PSIO.

Z zawodowych to tylko SO, UTK i NI. Wie ktoś co może być przyczyną tej różnicy?

Comments

Myślę że nie masz się czym przejmować, bo u nas jedna z klas pierwszych (1AI) też nie ma takiego przedmiotu jak Programowanie Strukturalne i Obiektowe. Natomiast nasza klasa (1BI) nie ma np. NI. Sytuacja odwraca się w klasie drugiej :). Poszperaj po stronie internetowej szkoły, gdzieś powinien być wykaz przedmiotów w danej klasie i ilości godzin z danego przedmiotu.

---

OK dzieki wielkie