Grade 9 · Divisibility and prime numbersCitește în română

Divisors of a number

Original: Divizorii unui număr

O(√n)C++1747 lines2 examples

The idea

Divisors come in pairs: if d divides n, then n / d divides n too, and one of them is at most the square root of n. So it is enough to try d from 1 while d * d <= n. To print them in increasing order we make two passes: first the small divisors d (going up), then their pairs n / d (going down), without repeating the root when n is a perfect square.

Original description (Romanian)

Divizorii vin în perechi: dacă d divide n, atunci și n / d divide n, iar unul dintre ei este cel mult rădăcina pătrată a lui n. Ajunge deci să încercăm d de la 1 cât timp d * d <= n. Ca să-i afișăm în ordine crescătoare, facem două treceri: întâi divizorii mici d (în sus), apoi perechile lor n / d (în jos), fără să repetăm rădăcina când n este pătrat perfect.

Complexity
O(√n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

12

Expected output

1 2 3 4 6 12
Example 2

Input

36

Expected output

1 2 3 4 6 9 12 18 36

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

divizorii-unui-numar.cpp
/*
 * Titlu: Divizorii unui număr
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Divizorii vin în perechi: dacă d divide n, atunci și n / d divide n,
 *            iar unul dintre ei este cel mult rădăcina pătrată a lui n. Ajunge
 *            deci să încercăm d de la 1 cât timp d * d <= n. Ca să-i afișăm în
 *            ordine crescătoare, facem două treceri: întâi divizorii mici d (în
 *            sus), apoi perechile lor n / d (în jos), fără să repetăm rădăcina
 *            când n este pătrat perfect.
 * Complexitate: O(√n)
 *
 * Exemplu
 * Intrare: 12
 * Ieșire: 1 2 3 4 6 12
 *
 * Exemplu
 * Intrare: 36
 * Ieșire: 1 2 3 4 6 9 12 18 36
 */
#include <iostream>
using namespace std;

int main()
{
    long long n, d;
    cin >> n;
    // prima trecere: divizorii d cu d * d <= n
    for (d = 1; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            cout << d << ' ';
        }
    }
    // a doua trecere: perechile n / d, de la d mare spre d mic
    for (d = d - 1; d >= 1; d--)
    {
        if (n % d == 0 && d * d != n)
        {
            cout << n / d << ' ';
        }
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.