Clasa a IX-a lecția 7
From Algopedia
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
#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;
}C++
#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;
}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;
#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;
}#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;
}// 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;
}Suma divizorilor unui numar
Varianta1:
#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;
}Varianta2 optimizat:
#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;
}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.
#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;
}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
Suma Divizori teorie
Suma divizori impari
#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;
}Numarul divizorilor Pari
#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;
}AfisareDivizoriComuni
Să se scrie un program care afișează divizorii comuni ai două numere naturale citite de la tastatură.
#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;
}Laborator
TEMA
Tema teorie
Usoare
Medii
