piątek 21 stycznia 2022 imieniny Agnieszki i Jarosława 1976 - Pierwszy lot naddźwiękowych samolotów Concorde
Do końca roku pozostało: 0 dni
Informatyka
Interaktywna mapa szkół
Język polski Historia WOS Sztuka (plastyka i muzyka) Języki obce Religia i etyka
Matematyka Fizyka i astronomia Chemia Biologia Przyroda Geografia Technika Informatyka
Przedmioty zawodowe WF Ścieżki edukacyjne Wychowanie przedszkolne Nauczanie zintegrowane Więcej
Algorytmy i programowanie - zestaw zadań

Liczby pierwsze

Liczbę naturalną n nazywamy liczbą pierwszą, jeśli posiada ona tylko dwa podzielniki: 1 oraz n.

Użytkownik wprowadza liczbę naturalną n (załóżmy, że n > 1). Podaj algorytm sprawdzania, czy n jest liczba pierwszą. (Np.: po wprowadzeniu liczby 2 program powinien wyświetlić komunikat „tak”, natomiast po wprowadzeniu liczby 22 powinien pojawić się komunikat „nie”).

Specyfikacja algorytmu:
 Dane wejściowe:
 liczba naturalna n (n>1)
 Dane wyjściowe:

 komunikat „tak” lub „nie” w zależności od tego, czy n jest
 liczbą pierwszą

a)    Przedstaw ten algorytm w formie opisu kolejnych kroków.

b)    Zaprezentuj ten algorytm w formie schematu blokowego.

c)    Napisz program realizujący ten algorytm w wybranym przez siebie języku programowania
       (Pascal, C, lub C++). Oto przykład działania takiego programu:

          Podaj liczbę naturalną:  2

          Tak, jest to liczba pierwsza.

          Podaj liczbę naturalną:  22
          Nie, nie jest to liczba pierwsza.

d)    Zaimplementuj ten algorytm w formie programu w języku Visual Basic lub skryptu w języku
       JavaScript. Oto przykładowa aplikacja:

     

Wprowadź liczbę naturalną:



Przykładowe rozwiązanie

Wszystkie podzielniki liczby n należą do zbioru {1, 2, ..., n – 1, n}. Jeśli n jest liczbą pierwszą, wtedy posiada tylko podzielniki 1 oraz n. Zatem jeśli n posiada jakikolwiek podzielnik ze zbioru {2, ..., n – 1}, to znaczy że nie jest ona liczba pierwszą. Jeśli natomiast nie ma ani jednego „niepożądanego” podzielnika, wtedy n jest pierwsza.

Działanie algorytmu opiera się zatem na sprawdzeniu, czy liczba n posiada jakiś niedozwolony podzielnik. W najprostszej wersji algorytmu można sprawdzić wszystkie interesujące nas podzielniki, od 2 do n – 1. Będziemy potrzebowali pomocniczej zmiennej p, reprezentującej kolejny podzielnik. Ponadto określamy, w jaki sposób będziemy oznaczać działanie znajdowania reszty z dzielenia (symbol „mod”). Oto stosowne uzupełnienie specyfikacji algorytmu:

Zmienna pomocnicza:
 liczba naturalna p – kolejny podzielnik liczby n
Notacja:
 a mod b oznacza resztę z dzielenia liczby a
 przez liczbę b


Opis kolejnych kroków – pkt a)

Krok 1:   Wczytaj liczbę n.
Krok 2:   Zmiennej p przypisz wartość 2.
Krok 3:   Jeśli p jest równe n, wtedy wypisz komunikat „tak” i zakończ działanie
 algorytmu. W przeciwnym razie przejdź do następnego kroku.
Krok 4:   Jeśli n mod p jest równe 0, wtedy wypisz komunikat „nie”
 i zakończ działanie algorytmu.
Krok 5:   Powiększ wartość zmiennej p o 1 i przejdź do kroku 3

 

Schemat blokowy – pkt b)

 

Program w języku Pascal – pkt c)

program LiczbaPierwsza;

{ Sprawdzanie, czy wprowadzona liczba jest pierwsza }

var
  n, p: integer;
begin
write('Podaj liczbę naturalną: ');
readln(n);
for p:=2 to n-1 do
  if n mod p = 0 then
    begin
    writeln('Nie, nie jest to liczba pierwsza');
    halt
    end;
writeln('Tak, jest to liczba pierwsza')
end.

Uwaga: Procedura halt powoduje natychmiastowe zakończenie wykonywania
pętli for i całego programu. 

Program w języku C++ – pkt d)

// Sprawdzanie, czy wprowadzona liczba jest pierwsza

#include <iostream>
#include <stdlib>

main()
{
  int n;
  cout << "Podaj liczbę naturalną: ";
  cin >> n;
  for(int p=2; p<n; p++)
    if(n % p == 0)
    {
      cout << "Nie, nie jest to liczba pierwsza" << endl;
      exit(0);
    }
  cout << "Tak, jest to liczba pierwsza" << endl;
}

Uwaga: Funkcja exit powoduje natychmiastowe zakończenie wykonywania programu. Jej argumentem jest liczba całkowita – kod zakończenia programu. Kod równy zeru oznacza prawidłowe zakończenie programu (brak błędu wykonania). Wartość kodu jest szczególnie istotna, jeśli piszemy programy na potrzeby systemu operacyjnego Linux. 

 

Program w języku Visual Basic – pkt e)

Pole tekstowe, na którym użytkownik wpisuje sprawdzaną liczbę, jest oznaczone jako Text1. Przycisk uruchamiający procedurę sprawdzającą jest oznaczony jako Command1. Komunikat wyświetlany jest przy użyciu procedury MsgBox.
 

 

 

Oto procedura stowarzyszona z przyciskiem Command1:

Private Sub Command1_Click()
  Dim n, p
  n = Val(Text1.Text)
  For p = 2 To n - 1
    If n Mod p = 0 Then
            MsgBox ("Nie")
      Exit Sub
    End If
  Next p
  MsgBox ("Tak")
End Sub


Program w języku JavaScript – pkt f)

Prezentujemy kompletny kod HTML strony WWW będącej rozwiązaniem zadania: 

 

<html>

  <head>
    <script language=javascript>
      function oblicz()
      {
        var n = eval(document.form1.n.value);
        for(var p=2; p<n; p++)
          if(n % p == 0)
          {
            alert("Nie");
            return;
          }
        alert("Tak");
      }
    </script>
  </head>

  <body>
    <h3 align=center>Liczba pierwsza</h3>
    <center>  
      <form name=form1>
       
Wprowadź liczbę naturalną:
       
<input type=text size=5 name=n>
        <br><br>
        <input type=button
              
value="Sprawdź, czy jest pierwsza"
              
onClick=oblicz()>
      </form>
    </center>
  </body>

</html>






Autor: dr Andrzej Dyrek, mgr Agnieszka Tarnówka-Stec
Komentarze + Dodaj komentarz
  • W Pascalu jak tworzy się instrukcje złozoną to poprzedza sie ją słowem begin, Informatyk (odpowiedzi: 0)
  • Nawiasem mówiac schemat blokowy nie do tego problemu totalna porazka.
  • C++, Animatex (odpowiedzi: 0)
  • C++ jest podobne do języka PAWN
  • SIŁA!, SIŁA! (odpowiedzi: 0)
  • Biorę Double-Blast`a i nie wiem co się dzieje...
  • algorytmy, Pan:** (odpowiedzi: 0)
  • nie wiem o co chodzi :PP
  • Poprawa błędu w C++!, Gniewo (odpowiedzi: 0)
  • #include <iostream> using namespace std; int main() Poprawcie ten początek wtedy rusza. A tak na marginesie to nie wiem jak wy te dzieci do nauki ścisłych przedmiotów chcecie jeżeli zamieszczacie listing nie sprawdzony. Pozdraiwiam!
  • Niezgodność ze standardami., Bronek (odpowiedzi: 0)
  • W przykładzie Java Script powinno być tak. <script language="JavaScript> </script>
  • w c++ liczona jest suma, a nie srednia, * znaczy, że muszę to pole podać? (odpowiedzi: 0)
  • w sumie to tyle... zapomnieli podzielić przez n ;)
  • gggg, gggg (odpowiedzi: 0)
  • co za nudy
  • Blad ???, Wojtas (odpowiedzi: 6)
  • Mam pytanie, czemu w kompilatorze Dev-C++ wyskakuje mi blad, podczas kompilacji ??
  • algorytm c+, student politechnika (odpowiedzi: 0)
  • buhahahhaha. Niezly portal i niezle ucza:) W szczegolnosci podobaja mi sie programy w c++. Ciekawe tylko czy ten doktor, ktory sie pod tym podpisuje kiedykolwiek mial indeks wyzszej uczelni w reku bo juz na pewno nie kierunku informatycznego. Krotko mowiac no comment;
  • schemat blokowy jest od innego zadania, aa (odpowiedzi: 0)
  • a
  • bład w schemacie blokowym algorytmu max(a,b,c,d), Agnieszka (odpowiedzi: 0)
  • schemat blokowy punkt b) nie przedstawia rozwiązania zadania.
  • Kto to pisał?, uczen 2 gimnazjum (odpowiedzi: 2)
  • Nie chciałbym być nie uprzejmy, zawsze uczy sie od tyłu? Przecież takie zadanie można rozwiązać dużo szybciej, stosując konstrukcje języka...
 
Nasi partnerzy:
MEN SchoolNet eTwinning Związek Powiatów Polskich PCSS
Cisco OFEK Przyjazna Szkoła Fundacja Junior FIO CEO
Parafiada net PR Orange IMAX Cinema City WSP TWP
IMAGE PPI-ETC ArcaVir Master Solution Device


Projekt Polski Portal Edukacyjny Interkl@sa
powstał i był realizowany w latach 2000-2011 dzięki wsparciu
Polsko-Amerykańskiej Fundacji Wolności.

W ramach naszej witryny stosujemy pliki cookies w celu świadczenia Państwu usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Państwa urządzeniu końcowym. Możecie Państwo dokonać w każdym czasie zmiany ustawień dotyczących cookies. Więcej szczegółów w naszej "Polityce Prywatności".


Pytania i uwagi: portal@interklasa.pl

Regulamin portalu /  Polityka prywatności /  Ochrona własności intelektualnej /  Zasady korzystania / 
Wyłączenie odpowiedzialności /  Biuro prasowe /  Zasady współpracy /  Redakcja /  Kontakt

Przejdź na stronę ucznia Przejdź na stronę nauczyciela Przejdź na stronę rodzica Certyfikat sieciaki.pl Przyjazna strona kidprotect.pl