Grade 9 · Divisibility and prime numbersCitește în română
Proper divisors of a number
Original: Divizorii proprii ai unui număr
The idea
Proper divisors are the divisors other than 1 and n. We use the same two passes as when printing all divisors, but start from d = 2, so 1 and its pair, n, are both left out. A prime number has no proper divisors.
Original description (Romanian)
Divizorii proprii sunt divizorii diferiți de 1 și de n. Folosim aceleași două treceri ca la afișarea tuturor divizorilor, dar pornim de la d = 2, deci lipsesc și 1, și perechea lui, n. Un număr prim nu are divizori proprii.
- Complexity
- O(√n)
- Grade
- Grade 9 (Clasa a IX-a)
Examples
Input
12
Expected output
2 3 4 6
Input
13
Expected output
nu are divizori proprii
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* Titlu: Divizorii proprii ai unui număr
* Clasa: 9
* Capitol: Divizibilitate și numere prime
* Descriere: Divizorii proprii sunt divizorii diferiți de 1 și de n. Folosim
* aceleași două treceri ca la afișarea tuturor divizorilor, dar
* pornim de la d = 2, deci lipsesc și 1, și perechea lui, n. Un număr
* prim nu are divizori proprii.
* Complexitate: O(√n)
*
* Exemplu
* Intrare: 12
* Ieșire: 2 3 4 6
*
* Exemplu
* Intrare: 13
* Ieșire: nu are divizori proprii
*/
#include <iostream>
using namespace std;
int main()
{
long long n, d;
int gasiti = 0;
cin >> n;
for (d = 2; d * d <= n; d++)
{
if (n % d == 0)
{
cout << d << ' ';
gasiti++;
}
}
for (d = d - 1; d >= 2; d--)
{
if (n % d == 0 && d * d != n)
{
cout << n / d << ' ';
gasiti++;
}
}
if (gasiti == 0)
{
cout << "nu are divizori proprii";
}
cout << '\n';
return 0;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.