01/10/2018, 11:17

Cải tiến bài toán in ra các ước của n

các anh chị giúp em với =-=’
em nghĩ mãi không có thuật toán nào nó ít vòng lặp cả ngoài cách dùng for từ 1->n =-=’

HK boy viết 13:25 ngày 01/10/2018

Bạn để ý rằng, nếu i là ước của n thì n / i cũng là ước của n.
Ta có thể giảm được kha khá trường hợp rồi:

for (int i = 1; i * i <= n; i++) // chỉ xét các ước i <= sqrt(n).
// điều kiện i * i <= n tương đương với i <= sqrt(n),
    if (n % i == 0) { // phát hiện có ước i
        if (i == n / i) cout << i << " "; // nếu n == k * k (hay n là số chính phương)
        // thì khi i == k, n / i == k == i -> nếu in ra i và n / i sẽ bị thừa 1 số,
        // do vậy ta chỉ cần in ra i
        else cout << i << " " << n / i << " ";
    }

Ta chỉ cần chạy sqrt(n) lần lặp thôi.

‏ viết 13:22 ngày 01/10/2018

sqrt(n) chính xác với mọi số nguyên luôn mà. Kiểm tra thử với 46340 số chính phương < 2^31 sẽ thấy nó đúng hết, i*i <= n ko chính xác hơn đâu

HK boy viết 13:26 ngày 01/10/2018

Thế là dùng