Strefa wyzwań

Już wiesz

Jakie własności mają liczby pierwszych oraz gdzie znajdują zastosowanie.
Jaka jest idea algorytmu sita Eratostenesa.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

Ćwiczenie 1

RF4NR2O3SALFT

Ćwiczenie 2

R1FB6U8BD5QH3

Ćwiczenie 3

RFAZAEL9GOAHH

Zastosowałeś algorytm Sito Erastotenesa. Które liczby będą liczbami pierwszymi? Możliwe odpowiedzi: 1. Wartości indeksów elementów tablicy, których zawartość wynosi fałsz, 2. Wartości indeksów elementów tablicy, których zawartość wynosi prawda, 3. Wartości elementów tablicy z zakresu [2, ... n], 4. , 5.

Ćwiczenie 4

R19G2UJL1EA63

Ile razy elementowi tablicy o indeksie 70 została przypisana wartość fałsz w algorytmie Sito Eratostenesa dla zbioru <2, ... 51> Tu uzupełnij

Ćwiczenie 5

Dana jest n‑elementowa tablica A wypełniona wartościami 1. Korzystając z algorytmu sita Eratostenesa, zmień zawartość tablicy tak, aby wartość 1 miały tylko te elementy tablicy, których indeksy są liczbami pierwszymi, pozostałe elementy powinny mieć wartość 0.

Specyfikacja problemu:

Dane:

n – liczba elementów tablicy
A – tablica liczb wypełniona wartościami 1

Wynik:

Zmodyfikowana tablica A; wartość 1 przechowują wyłącznie komórki, których indeksy są liczbami pierwszymi; wartość 0 przechowują komórki, których indeksy są liczbami złożonymi.

RF8PTFKP6UX8J

Ćwiczenie 6

RTAM6FJGU9E44

Ćwiczenie 7

Zmodyfikuj algorytm sita Eratostenesa tak, aby wartością elementu tablicy była liczba dzielników właściwych, które są liczbami pierwszymi (dzielniki będące liczbami pierwszymi, oprócz dzielników o wartości danego indeksu).

Specyfikacja problemu:

Dane:

n – liczba elementów tablicy
A – tablica liczb wypełniona wartościami 0

Wynik:

Zmodyfikowana tablica A; wartość kryjąca się pod indeksem i przechowuje liczbę dzielników właściwych, które są liczbami pierwszymi.

Przykład:

Liczba 7 będzie miała 0 dzielników, ponieważ nie bierzemy pod uwagę dzielnika 7.

R1SDZEUAVMJAK

Ćwiczenie 8

Piotr Bajtocki prowadzi firmę budowlaną. Zgodnie z prawem ma obowiązek zaopatrzyć swoich pracowników w wodę. Butelki wody o pojemności 1,5 litra są pakowane w zgrzewkach. W każdej ze zgrzewek zapakowano pewną liczbę butelek. Liczba ta jest liczbą pierwszą. Najmniejsza zgrzewka opakowuje m butelek; największa n. Litr wody kosztuje x złotych. Budżet Piotra wynosi y złotych. Jak dużą zgrzewkę wody może kupić?

Jeśli liczba butelek, które w zgrzewce może kupić pan Bajtocki, jest większa od n, oznacza to, że jego budżet pozwala na zakup największej zgrzewki.

W swoim rozwiązaniu nie wykorzystuj funkcji sqrt.

Swoje rozwiązanie przetestuj dla x wynoszącego 0,80; y równego 70, n równego 97, m wynoszącego 5.

Specyfikacja problemu:

Dane:

x – cena litra wody; liczba zmiennoprzecinkowa dodatnia
y – budżet Piotra; liczba zmiennoprzecinkowa dodatnia
n – maksymalna liczba butelek w zgrzewce; liczba naturalna; $n \gt 11$
m – liczba butelek w najmniejszej zgrzewce; liczba naturalna; $m \geq 5$

Wynik:

Na standardowym wyjściu program wypisuje największą liczbę butelek w zgrzewce, która mieści się w budżecie Piotra.

RnOm6OMmbTwbK1

Przykładowe rozwiązanie zadania:

n = 97
m = 5
x = 0.8
y = 70.00

#wyznaczanie sita i zwiększamy n
n += 1
sito = [True] * n

i = 2
while i * i < n:
	if sito[i]:
		j = i * i
		while j < n:
			sito[j] = False
			j = j + i
	i += 1

cena_butelki = x * 1.5
ile_maksymalnie_moze_kupic = int(y / cena_butelki)

if ile_maksymalnie_moze_kupic > n-1:
	ile_maksymalnie_moze_kupic = n-1
elif ile_maksymalnie_moze_kupic < m:
	ile_maksymalnie_moze_kupic = 0
else:
	while sito[ile_maksymalnie_moze_kupic] == False:
		ile_maksymalnie_moze_kupic = ile_maksymalnie_moze_kupic - 1

print(ile_maksymalnie_moze_kupic)

Plik z programem do pobrania:

R12AKOXJU4QQE

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 594.00 B w języku polskim

Ćwiczenie 9

Zygmunt Bajtek otrzymał od rodziców na urodziny prezent – zegarek analogowy.
Zafascynowany tym podarkiem postanowił policzyć, ile razy wskazówka minutowa wskaże liczbę pierwszą. Uzyskawszy tę wiedzę, policzył kąty $\phi$ między osią biegnącą od środka tarczy do minutowego 0, a wskazówką minutową wskazującą liczby pierwsze.

Zapoznaj się z ilustracją załączoną do zadania, przedstawiono na niej przykładowe oznaczenie kąta.

Napisz program, który w kolejnych liniach wypisze kolejne wartości $\phi$ zaczynając od 3‑ciej minuty.

Specyfikacja problemu:

Dane:

A – 61‑elementowa tablica wartości logicznych wypełniona wartościami true

Wynik:

Na standardowym wyjściu program wypisuje w kolejnych wierszach wartości kąta $\phi$ .

RXiCTwFRWcmHK

Ilustracja przedstawia okręg. Od środka poprowadzono trzy promienie. Pionowy od środka do góry. W miejscu przecięcia z okręgiem zaznaczono wartość zero. Drugi promień poprowadzono po skosie w dół w prawą stronę. W miejscu przecięcia z okręgiem zaznaczono wartość dwadzieścia trzy. Trzeci promień poprowadzono po skosie w dół w lewą stronę, gdzie zaznaczono wartość trzydzieści siedem w miejscu przecięcia promienia z obwodem okręgu. Ponadto w jednej czwartej obwodu, licząc od miejsca, w którym zaznaczono zero, zapisano wartość piętnaście. W połowie zaznaczono wartość trzydzieści, natomiast w trzech czwartych wartość czterdzieści pięć. Ponadto pomiędzy pierwszym a drugim promieniem, idąc zgodnie z ruchem wskazówek zegara, zaznaczono kąt równy fi jeden, a pomiędzy pierwszym i trzecim, również zgodnie z ruchem wskazówek zegara, zaznaczono kąt fi dwa. — Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Rpfg3PrVVVKwO

Ćwiczenie 10

Hipoteza Goldbacha zakłada, że każda liczba naturalna parzysta większa od 2 jest sumą dwóch liczb pierwszych. Napisz program weryfikujący hipotezę Goldbacha dla liczb parzystych nie większych od n.

Swoje rozwiązanie zweryfikuj dla n wynoszącego 1000.

Specyfikacja problemu:

Dane:

n – parzysta liczba naturalna dodatnia

Wynik:

Na standardowym wyjściu program wypisuje równania potwierdzające hipotezę Goldbacha, zgodnie z poniższym schematem; NIE w przeciwnym przypadku.

Przykład wyjścia:

Lewy składnik dodawania jest mniejszy od prawego; kolejne sumy wypisywane są rosnąco:

2 + 2 = 4
3 + 3 = 6
3 + 5 = 8
...
7 + 991 = 998

R12dXRGRuUcC31

Przykładowe rozwiązanie zadania:

Linia 1. n znak równości 1000. Linia 3. if n procent 2 znak równości znak równości 1 dwukropek. Linia 4. print otwórz nawias okrągły apostrof Wprowadzono liczbe nieparzysta wykrzyknik apostrof zamknij nawias okrągły. Linia 5. exit otwórz nawias okrągły zamknij nawias okrągły. Linia 7. sito znak równości otwórz nawias kwadratowy True zamknij nawias kwadratowy asterysk n. Linia 9. i znak równości 2. Linia 10. while i asterysk i otwórz nawias ostrokątny n dwukropek. Linia 11. if sito otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. while j otwórz nawias ostrokątny n dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości False. Linia 15. j znak równości j plus i. Linia 16. i plus znak równości 1. Linia 18. liczba podkreślnik liczb podkreślnik pierwszych znak równości 0. Linia 19. liczby podkreślnik pierwsze znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 20. for i in range otwórz nawias okrągły 2 przecinek len otwórz nawias okrągły sito zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 21. if sito otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 22. liczba podkreślnik liczb podkreślnik pierwszych plus znak równości 1. Linia 23. liczby podkreślnik pierwsze kropka append otwórz nawias okrągły i zamknij nawias okrągły. Linia 25. for parzysta in range otwórz nawias okrągły 4 przecinek len otwórz nawias okrągły sito zamknij nawias okrągły plus 1 przecinek 2 zamknij nawias okrągły dwukropek. Linia 26. lewa znak równości 0. Linia 27. prawa znak równości liczba podkreślnik liczb podkreślnik pierwszych minus 1. Linia 28. while lewa otwórz nawias ostrokątny znak równości prawa dwukropek. Linia 29. if liczby podkreślnik pierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy plus liczby podkreślnik pierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy znak równości znak równości parzysta dwukropek. Linia 30. break. Linia 31. elif liczby podkreślnik pierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy plus liczby podkreślnik pierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy otwórz nawias ostrokątny parzysta dwukropek. Linia 32. lewa plus znak równości 1. Linia 33. else dwukropek. Linia 34. prawa minus znak równości 1. Linia 36. if liczby podkreślnik pierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy plus liczby podkreślnik pierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy znak równości znak równości parzysta dwukropek. Linia 37. print otwórz nawias okrągły str otwórz nawias okrągły liczby podkreślnik pierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy zamknij nawias okrągły plus cudzysłów plus cudzysłów plus str otwórz nawias okrągły liczby podkreślnik pierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy zamknij nawias okrągły plus cudzysłów znak równości cudzysłów plus str otwórz nawias okrągły parzysta zamknij nawias okrągły zamknij nawias okrągły. Linia 38. continue. Linia 40. print otwórz nawias okrągły apostrof NIE apostrof zamknij nawias okrągły. Linia 41. exit otwórz nawias okrągły zamknij nawias okrągły.

n = 1000

if n % 2 == 1:
	print('Wprowadzono liczbe nieparzysta!')
	exit()

sito = [True] * n

i = 2
while i * i < n:
	if sito[i]:
		j = i * i
		while j < n:
			sito[j] = False
			j = j + i
	i += 1

liczba_liczb_pierwszych = 0
liczby_pierwsze = []
for i in range(2, len(sito)):
	if sito[i]:
		liczba_liczb_pierwszych += 1
		liczby_pierwsze.append(i)

for parzysta in range(4, len(sito) + 1, 2):
	lewa = 0
	prawa = liczba_liczb_pierwszych - 1
	while lewa <= prawa:
		if liczby_pierwsze[lewa] + liczby_pierwsze[prawa] == parzysta:
			break
		elif liczby_pierwsze[lewa] + liczby_pierwsze[prawa] < parzysta:
			lewa += 1
		else:
			prawa -= 1

	if liczby_pierwsze[lewa] + liczby_pierwsze[prawa] == parzysta:
		print(str(liczby_pierwsze[lewa]) + " + " + str(liczby_pierwsze[prawa]) + " = "  + str(parzysta))
		continue

	print('NIE')
	exit()

Plik z programem do pobrania:

RQGRVC1TLLGK3

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 878.00 B w języku polskim

Implementacja algorytmu