Bella at 18:48, 21 November 2022

2022-11-21T18:48:10Z

New page

'''Note de curs: prof. Isabela Coman'''
=Lectie=
== Afisarea divizorilor unui numar in ordine crescatoare ==
Fie un numar n natural. Sa se afiseze divizorii acestuia in ordine crescatoare.
==== Varianta1 ====
Aceasta varianta propune verificarea tuturor numerelelor de la 1 la n si afisarea doar a celor ce divid numarul n.

'''Pseudocod'''
intreg n, d
citeste n
d = 1
cat_timp( d <= n )
if( n % d == 0 )
scrie d, " "
d = d + 1;

'''C'''
<syntaxhighlight>
#include <stdio.h>
int main(){
int n, d;

scanf("%d", &n);

d = 1;
while( d <= n ){
if( n % d == 0 )
printf("%d ", d);
d = d + 1;
}
return 0;
}
</syntaxhighlight>
'''C++'''
<syntaxhighlight>
#include <stdio.h>
using namespace std;
int main(){
int n, d;

cin >> n;

d = 1;
while( d <= n ){
if( n % d == 0 )
cout << d << '\n';
d = d + 1;
}
return 0;
}
</syntaxhighlight>

==== Varianta2 optima ====
Stim ca toti divizorii unui numar de pana in radicalul sau au ca si divizor corespondent un divizor de dupa radical si anume, presupunand un d ca divizor de pana in radical, n/d este perechea sa de dupa radical.

'''Pseudocod'''
intreg n, d
citeste n
d = 1
cat_timp( d < sqrt( n ) ) //sqrt(n) se considera parte intreaga
if( n mod d == 0 )
scrie d, " "
d = d + 1;
d = sqrt( n )
cat_timp( d >= 1 ) //sqrt(n) se considera parte intreaga
if( n mod d == 0 )
scrie n / d, " "
d = d - 1;

<syntaxhighlight>
#include <stdio.h>
#include <math.h>
int main(){
int n, d;

scanf("%d", &n);
// afisam mai intai divizorii de pana in radical
// vom parcurge deci sqrt(n) numere
d = 1;
while( d * d < n ){
if( n % d == 0 )
printf("%d\n", d);
d = d + 1;
}
// afisam divizorii de dupa radical
// parcurgem divizorii de pana in radical in ordine inversa
// si afisam perechea fiecaruia de dupa radical
// vom parcurge deci tot sqrt(n) numere
d = sqrt (n);
while( d >= 1 ){
if( n % d == 0 )
printf("%d\n", n/d);
d = d - 1;
}
return 0;
}
</syntaxhighlight>
<syntaxhighlight>
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n, d;

cin >> n;
// afisam mai intai divizorii de pana in radical
// vom parcurge deci sqrt(n) numere
d = 1;
while( d * d < n ){
if( n % d == 0 )
cout << d << '\n';
d = d + 1;
}
// afisam divizorii de dupa radical
// parcurgem divizorii de pana in radical in ordine inversa
// si afisam perechea fiecaruia de dupa radical
// vom parcurge deci tot sqrt(n) numere
d = sqrt (n);
while( d >= 1 ){
if( n % d == 0 )
cout << n / d << '\n';
d = d - 1;
}
return 0;
}
</syntaxhighlight>
<syntaxhighlight>
// fara sqrt
#include <iostream>

using namespace std;
int main(){
int n, d;

cin >> n;
// afisam mai intai divizorii de pana in radical
// vom parcurge deci sqrt(n) numere
d = 1;
while( d * d < n ){
if( n % d == 0 )
cout << d << '\n';
d = d + 1;
}
// afisam divizorii de dupa radical
// parcurgem divizorii de pana in radical in ordine inversa
// si afisam perechea fiecaruia de dupa radical
// vom parcurge deci tot sqrt(n) numere

if ( d * d > n ) // daca am depasit radicalul, scadem 1 din d
d --;
while( d >= 1 ){
if( n % d == 0 )
cout << n / d << '\n';
d = d - 1;
}
return 0;
}</syntaxhighlight>

== Suma divizorilor unui numar ==
Varianta1:
<syntaxhighlight>
#include <stdio.h>
int main() {
int n, d, s;
scanf( "%d", &n );
printf( "Divizorii lui %d sunt:", n );

s = 0;
d = 1;
while ( d <= n ) {
if ( n % d == 0 )
s = s + d;
d = d + 1;
}
printf( "%d", s );
return 0;
}
</syntaxhighlight>
Varianta2 optimizat:

<syntaxhighlight>
#include <stdio.h>
int main(){
long long n, s, d;

scanf("%lld", &n);
s = 0;
d = 1;
while( d * d < n ){ // ne oprim cu d pana in radicalul numarului n
if( n % d == 0 )
s = s + d + n / d; // adaugam la suma si pe d si perechea sa de dupa radical
d = d + 1;
}

// aici d va fi fie egal cu radical din n daca n e patrat perfect, fie mai mare decat radical din n

if( d * d == n ) // daca n e patrat perfect,
s = s + d; // vom adauga radical din n doar o data la suma
printf("%lld\n", s);
return 0;
}
</syntaxhighlight>

== Primalitate ==
Fie un numar n. Sa se afiseze mesajul "DA" daca numarul este prim si mesajul "NU" in caz contrar.
Rezolvare: Vom cauta un divizor al numarului n parcurgand toate numerele de la 2 pana la radical din n. Daca nu vom gasi nici un divizor, atunci numarul este prim.
<syntaxhighlight>
#include <stdio.h>
int main() {
int n, d;
scanf( "%d", &n );
d = 2;
while ( d * d <= n && n % d > 0 )
d = d + 1;
if ( d * d > n && n > 1 )
printf( "DA" );
else
printf( "NU" );
return 0;
}
</syntaxhighlight>

==Divizori primi==
Sa se afiseze cati divizori primi are un număr n?
Tendinta multora cand e vorba de aceasta problema este de a pcuarcurge toti divizorii si de a-i verifica pe fiecare in parte daca este prim. Vom invata in lectia urmatoare cum descompunem in factori primi un numar.

= Laborator =
==Divizorii unui numar==
==== [https://www.pbinfo.ro/?pagina=probleme&id=376 Suma Divizori] teorie====
==== [https://www.pbinfo.ro/?pagina=probleme&id=387 Suma divizori impari]====
<syntaxhighlight>
#include <stdio.h>
int main(){
long long n, s, d;

scanf("%lld", &n);
s = 0;
d = 1;
while( d * d < n ){
if( n % d == 0 ){
if( d % 2 ){
s = s + d; //printf("%lld\n", d);
}
if( n / d % 2 ){
s = s + n / d; //printf("%lld\n", n/d);
}
}
d = d + 1;
}
if( d * d == n && d % 2 )
s = s + d;
printf("%lld\n", s);
return 0;
}
</syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=388 Numarul divizorilor Pari]====
<syntaxhighlight>
#include <stdio.h>
int main(){
long long n, c, d;

scanf("%lld", &n);
c = 0;
d = 1;
while( d * d < n ){
if( n % d == 0 ){
if( d % 2 == 0){
c = c + 1; //printf("%d\n", d);
}
if( n / d % 2 == 0){
c = c + 1; //printf("%d\n", n/d);
}
}
d = d + 1;
}
if( d * d == n && d % 2 == 0 )
c = c + 1;
printf("%lld\n", c);
return 0;
}
</syntaxhighlight>
==== [https://www.pbinfo.ro/?pagina=probleme&id=61 AfisareDivizoriComuni]====
Să se scrie un program care afișează divizorii comuni ai două numere naturale citite de la tastatură.
<syntaxhighlight>
#include <stdio.h>
#include <math.h>

int main(){
int a, b, d;

scanf( "%ld%d", &a, &b );
// pun in a valoarea cea mai mica dintre a si b
if ( a > b ){
d = a;
a = b;
b = d;
}
// parcurg toti divizorii d ai lui a de pana in radical
// si ma intreb daca sunt si divizori ai lui b
d = 1;
while( d * d < a ){
if ( a % d == 0 && b % d == 0 )
printf( "%d ", d ) ;
d = d + 1;
}
// parcurg toti divizorii d ai lui a de pana in radical,
// daca d e divizor al lui a si n/d e divizor al lui a
// verific daca n/d este si divizori ai lui b
d = sqrt ( a );
while( d * d >= 1 ){
if ( a % d == 0 && b % ( a / d ) == 0 )
printf( "%d ", a / d ) ;
d = d - 1;
}
return 0;
}
</syntaxhighlight>

= Laborator =

== TEMA ==
=== Tema teorie ===
Usoare
* [https://www.pbinfo.ro/?pagina=probleme&id=408 Divizorii Oglinditului]
* [https://www.pbinfo.ro/?pagina=probleme&id=64 NumarPerfect]
* [https://www.pbinfo.ro/?pagina=probleme&id=445 PseudoPerfect]
* [https://www.pbinfo.ro/?pagina=probleme&id=373 nPrime]
* [https://www.pbinfo.ro/?pagina=detalii-evaluare&id=6301021 DivizoriPariInterval]
Medii
* [https://www.pbinfo.ro/?pagina=probleme&id=2745 intrebari] numarul de divizori
* [https://www.pbinfo.ro/?pagina=probleme&id=1574 Prietene] ( suma divizori )
* [https://www.pbinfo.ro/?pagina=probleme&id=245 NrDivMax]
* [https://www.pbinfo.ro/?pagina=probleme&id=380 aprim1]
* [https://www.pbinfo.ro/?pagina=probleme&id=381 aprim2]
* [https://www.pbinfo.ro/?pagina=probleme&id=374 nprime1]

Clasa a IX-a lecția 7 - Revision history

Bella at 18:48, 21 November 2022