Sovago Rares-Andrei at 06:53, 2 April 2023

2023-04-02T06:53:11Z

← Older revision		Revision as of 06:53, 2 April 2023
Line 40:		Line 40:
	n = int(sir_input.strip())		n = int(sir_input.strip())
	if n < 2:		if n < 2:
	return ~~False~~		return "Datele nu corespund restricțiilor impuse."
	return ~~True~~		print("Datele sunt introduse corect.")
			return "Corect"
	except ValueError:		except ValueError:
	return ~~False~~		return "Datele nu corespund restricțiilor impuse."


Line 93:		Line 94:


	~~def main():~~		if __name__ == "__main__":
	~~"""Funcția principală care validează datele de intrare și afișează rezultatul în fișierul de ieșire."~~""
	with open("rabin-miller.in", "r") as f, open("rabin-miller.out", "w") as w:		with open("rabin-miller.in", "r") as f, open("rabin-miller.out", "w") as w:
	sir_input = f.readline().strip()		sir_input = f.readline().strip()
	~~if not~~ este_input_valid(sir_input):		validitate_input = este_input_valid(sir_input)
	print(~~"Datele nu corespund restricțiilor impuse."~~)		if validitate_input != "Corect":
			print(validitate_input)
	exit(0)		exit(0)
	~~elif~~ este_numar_prim(int(sir_input)):		if este_numar_prim(int(sir_input)):
	w.write("DA")		w.write("DA\n")
	else:		else:
	w.write("NU")		w.write("NU\n")
	~~print("Datele sunt introduse corect.")~~



	~~# Apelăm funcția principală pentru a rula programul.~~
	~~main()~~


Line 115:		Line 115:


	~~'''Explicatie'''~~
	~~Acest cod implementează un program care primește un număr natural n în fișierul de intrare și verifică dacă acesta este prim folosind algoritmul Miller-Rabin.~~

	Înainte de a efectua testul de primalitate, se validează datele de intrare pentru a se asigura că n este un număr natural valid mai mare sau egal cu 2. Dacă datele de intrare nu respectă aceste restricții, programul afișează un mesaj corespunzător și se oprește prin apelul funcției exit(0).

	Dacă datele sunt valide, programul continuă și efectuează testul de primalitate folosind funcția este_numar_prim. Aceasta implementează testul Miller-Rabin, care este o metodă probabilistică pentru a verifica dacă un număr este prim sau nu.

	Dacă n este prim, funcția este_numar_prim returnează True, altfel returnează False. În funcția principală main, dacă n este prim, programul afișează "DA" în fișierul de ieșire, altfel afișează "NU". La sfârșit, se afișează un mesaj corespunzător în consolă.

			</syntaxhighlight>


			==Explicatie==
			este_input_valid(sir_input): Această funcție primește un șir de caractere ca intrare și verifică dacă acesta reprezintă un număr natural valid. În cazul în care șirul este valid, funcția returnează "Corect". În caz contrar, funcția returnează "Datele nu corespund restricțiilor impuse.".

			este_numar_prim(n): Această funcție primește un număr întreg pozitiv n ca intrare și verifică dacă acesta este un număr prim utilizând testul de primalitate Miller-Rabin. În cazul în care n este prim, funcția returnează True. În caz contrar, funcția returnează False.

			calculeaza_sd(x): Această funcție primește un număr întreg pozitiv x ca intrare și calculează cea mai mare putere a lui 2, denumită s, astfel încât x poate fi scris sub forma x = d * 2^s.

			Funcția este utilizată în implementarea testului de primalitate Miller-Rabin pentru a calcula valorile s și d necesare.

	~~</syntaxhighlight>~~		if __name__ == "__main__":: Această condiție verifică dacă programul este rulat direct sau importat ca modul într-un alt program. În cazul în care programul este rulat direct, codul din blocul de instrucțiuni este executat. În caz contrar, blocul de instrucțiuni nu este executat.
			În programul dat, acest bloc verifică dacă datele de intrare sunt valide, iar în caz afirmativ, utilizează funcția este_numar_prim(n) pentru a verifica dacă numărul este prim sau nu. În funcție de rezultatul verificării, se scrie "DA" sau "NU" în fișierul de ieșire.

Sovago Rares-Andrei: Pagină nouă: == Cerința == Se dă un număr natural '''n'''. Să se afișeze '''DA''' dacă numărul este prim altfel se afișează '''NU'''. == Date de intrare == Fișierul de intrare '''rabin-miller.in''' conține pe prima linie numărul '''n'''. == Date de ieșire == Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", fișierul de ieșire '''rabin-miller.out''' va conține pe prima linie '''DA''' sau '''NU''' după caz. În cazul în care datele nu respectă...

2023-03-30T17:35:44Z

Pagină nouă: == Cerința == Se dă un număr natural '''n'''. Să se afișeze '''DA''' dacă numărul este prim altfel se afișează '''NU'''. == Date de intrare == Fișierul de intrare '''rabin-miller.in''' conține pe prima linie numărul '''n'''. == Date de ieșire == Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", fișierul de ieșire '''rabin-miller.out''' va conține pe prima linie '''DA''' sau '''NU''' după caz. În cazul în care datele nu respectă...

New page

== Cerința ==
Se dă un număr natural '''n'''. Să se afișeze '''DA''' dacă numărul este prim altfel se afișează '''NU'''.
== Date de intrare ==
Fișierul de intrare '''rabin-miller.in''' conține pe prima linie numărul '''n'''.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran:
"Datele sunt introduse corect.", fișierul de ieșire '''rabin-miller.out''' va conține pe prima linie '''DA''' sau '''NU''' după caz. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
== Restricții și precizări ==
:'''n''' se poate reprezenta pe 8 Bytes
== Exemple ==
===Exemplul 1===
; ''rabin-miller.in''
:5
; ''ecran''
:Datele sunt introduse corect.
; ''rabin-miller.out''
: DA
===Exemplul 2===
; ''rabin-miller.in''
:13
; ''ecran''
:Datele sunt introduse corect.
; ''rabin-miller.out''
: DA
===Exemplul 3===
; ''rabin-miller.in''
:abc
; ''ecran''
:Datele nu corespund restricțiilor impuse.

<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 3057 - Rabin Miller
def este_input_valid(sir_input):
"""Verifică dacă șirul de intrare este un număr natural valid."""
try:
n = int(sir_input.strip())
if n < 2:
return False
return True
except ValueError:
return False

def este_numar_prim(n):
"""Implementarea testului de primalitate Miller-Rabin, garantată să fie corectă."""
import math

def calculeaza_sd(x):
"""Calculează (s: int, d: int) pentru care x = d*2^s """
if not x:
return 0, 0
s = 0
while 1:
if x % 2 == 0:
x //= 2
s += 1
else:
return s, x

if n <= 2:
return n == 2

# n - 1 = d*2^s
s, d = calculeaza_sd(n - 1)

if not s:
return False # divizibil cu 2!

log2n = int(math.log(n) / math.log(2)) + 1

# Conform hipotezei lui Riemann, este imposibil
# ca toate numerele sub acest prag să fie "strong liars".
# Prin urmare, numărul este garantat să fie prim dacă nu se găsește o contradicție.
prag = min(n, 2*log2n*log2n+1)

for a in range(2, prag):
# Din mica teoremă a lui Fermat, dacă n este prim atunci a^(n-1) % n == 1
# Prin urmare, trebuie să fie adevăratul dacă n este într-adevăr prim:
if pow(a, d, n) != 1:
for r in range(0, s):
if -pow(a, d*2**r, n) % n == 1:
break
else:
# Contrazice mica teoremă a lui Fermat, prin urmare nu este prim.
return False

# Nu s-a găsit nicio contradicție, prin urmare n trebuie să fie prim.
return True

def main():
"""Funcția principală care validează datele de intrare și afișează rezultatul în fișierul de ieșire."""
with open("rabin-miller.in", "r") as f, open("rabin-miller.out", "w") as w:
sir_input = f.readline().strip()
if not este_input_valid(sir_input):
print("Datele nu corespund restricțiilor impuse.")
exit(0)
elif este_numar_prim(int(sir_input)):
w.write("DA")
else:
w.write("NU")
print("Datele sunt introduse corect.")

# Apelăm funcția principală pentru a rula programul.
main()

'''Explicatie'''
Acest cod implementează un program care primește un număr natural n în fișierul de intrare și verifică dacă acesta este prim folosind algoritmul Miller-Rabin.

Înainte de a efectua testul de primalitate, se validează datele de intrare pentru a se asigura că n este un număr natural valid mai mare sau egal cu 2. Dacă datele de intrare nu respectă aceste restricții, programul afișează un mesaj corespunzător și se oprește prin apelul funcției exit(0).

Dacă datele sunt valide, programul continuă și efectuează testul de primalitate folosind funcția este_numar_prim. Aceasta implementează testul Miller-Rabin, care este o metodă probabilistică pentru a verifica dacă un număr este prim sau nu.

Dacă n este prim, funcția este_numar_prim returnează True, altfel returnează False. În funcția principală main, dacă n este prim, programul afișează "DA" în fișierul de ieșire, altfel afișează "NU". La sfârșit, se afișează un mesaj corespunzător în consolă.

</syntaxhighlight>

3057 - Rabin Miller - Revision history

Sovago Rares-Andrei at 06:53, 2 April 2023