Cerința
Marinel a învăţat la şcoală despre divizibilitatea numerelor naturale. Un număr natural nenul a este divizor al numărului natural nenul b dacă restul împărţirii lui b la a este 0. De exemplu, numărul 3 este divizor al lui 12 iar numărul 4 nu este divizor al lui 15. Un număr natural nenul n este număr prim dacă are doar 2 divizori: 1 şi n. De exemplu, numărul 7 este număr prim deoarece îi are ca divizori doar pe 1 şi 7 iar numărul 21 nu este număr prim deoarece îi are ca divizori pe 1, 3, 7 şi 21. Scrieţi un program care să îl ajute pe Marinel să îşi verifice tema primită pentru acasă.
Fiind date numărul n al numerelor din şir şi numerele din şir, să se determine:
Cerința
Marinel a învăţat la şcoală despre divizibilitatea numerelor naturale. Un număr natural nenul a este divizor al numărului natural nenul b dacă restul împărţirii lui b la a este 0. De exemplu, numărul 3 este divizor al lui 12 iar numărul 4 nu este divizor al lui 15. Un număr natural nenul n este număr prim dacă are doar 2 divizori: 1 şi n. De exemplu, numărul 7 este număr prim deoarece îi are ca divizori doar pe 1 şi 7 iar numărul 21 nu este număr prim deoarece îi are ca divizori pe 1, 3, 7 şi 21. Scrieţi un program care să îl ajute pe Marinel să îşi verifice tema primită pentru acasă.
Fiind date numărul n al numerelor din şir şi numerele din şir, să se determine:
1) divizorii celui mai mare număr din şir, inclusiv 1 şi el însuşi;
2) numerele prime din şir;
3) numerele care sunt divizori ai tuturor numerelor din şir.
Date de intrare
Fişierul de intrare divizori2.in conține pe prima linie un număr natural P, pe a doua linie un număr natural n reprezentând numărul de numere din şir şi pe a treia linie cele n numere naturale din şir, separate prin spaţii.
Date de ieșire
Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerinţă:
fişierul divizori2.out va conţine pe prima linie doar divizorii celui mai mare număr din şir.
Dacă valoarea lui P este 2, se va rezolva doar punctul 2) din cerinţă:
fişierul divizori2.out va conţine pe prima linie doar numerele prime din şir sau numărul -1 dacă şirul nu conţine numere prime.
Dacă valoarea lui P este 3, se va rezolva numai punctul 3) din cerinţă:
fişierul divizori2.out va conţine pe prima linie doar numerele care sunt divizori ai tuturor numerelor din şir.
Restricții și precizări
- valoarea lui P poate să fie doar 1 sau 2 sau 3;
- numărul natural n este cuprins între 2 şi 1000;
- numerele din şir sunt numere naturale nenule cu cel mult 6 cifre;
- pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte;
- pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 30 de puncte;
- pentru rezolvarea corectă a celei de-a treia cerinţe se acordă 40 de puncte;
Exemplu1:
divizori2.in
1 7 12 18 8 4 13 6 17
divizori2.out
1 2 3 6 9 18
Explicație
P=1 deci se rezolvă prima cerinţă.
Cel mai mare număr din şir este 18.
Divizorii numărului 18 sunt 1, 2, 3, 6, 9 şi 18.
Exemplu2:
divizori2.in
2 7 12 18 8 4 13 6 17
divizori2.out
13 17
Explicație
P=2 deci se rezolvă a doua cerinţă.
Numerele prime din şir sunt 13 şi 17.
Exemplu3:
divizori2.in
2 7 12 18 8 4 12 6 15
divizori2.out
-1
Explicație
P=2 deci se rezolvă a doua cerinţă.
Nu sunt numere prime în şir.
Exemplu4:
divizori2.in
3 4 70 42 21 35
divizori2.out
1 7
Explicație
P=3 deci se rezolvă a treia cerinţă.
Divizorii lui 70 sunt 1, 2, 5, 7, 10, 14, 35 şi 70.
Divizorii lui 42 sunt 1, 2, 3, 6, 7, 14, 21 şi 42.
Divizorii lui 21 sunt 1, 3, 7 şi 21.
Divizorii lui 35 sunt 1, 5, 7 şi 35.
Numerele care sunt divizori ai tuturor numerelor din şir sunt 1 şi 7.
#include <bits/stdc++.h>
using namespace std;
ifstream fin("divizori2.in");
ofstream fout("divizori2.out");
int prim(long long n)
{
if(n == 0 || n == 1) return 0;
if(n == 2) return 1;
if(n % 2 == 0) return 0;
else for(int d = 3 ; d*d <= n ; d += 2) if(n % d == 0) return 0;
return 1;
}
int main()
{
int n , x , p , maxi = -1 , a , b , r , d, ok = 0;
fin >> p >> n;
if(p == 1)
{
for(int i = 1 ; i <= n ; ++i)
{
fin >> x;
{
if(x > maxi) maxi = x;
}
}
for(int i = 1 ; i <= maxi ; ++i)
{
if(maxi % i == 0) fout << i <<" ";
}
}
if(p == 2)
{
for(int i = 1 ; i <= n ; ++i)
{
fin >> x;
{
if(prim(x)) {fout << x << " ";ok = 1;}
}
}
if(ok == 0) fout << -1;
}
if(p == 3)
{
fin >> a;
for(int i = 1 ; i < n ; ++i)
{
fin >> b;
int b1 = b;
while(b != 0)
{
r = a % b;
a = b;
b = r;
}
d = a;
}
for(int i = 1 ; i <= d ; ++i)
{
if(d % i ==0) fout << i <<" " ;
}
}
fin.close();
fout.close();
return 0;
}
