Factors of a Number

easy Number Problems

Problem

Read a positive integer and print all its factors (divisors) in ascending order on one line, separated by a space.

Constraints

  • 1 <= n <= 10^12 for the pair version, 1 <= n <= 10^7 for the simple version

Examples

Input

12

Output

1 2 3 4 6 12

Solutions

Brute forceTime O(n)Space O(k)

We test all numbers from 1 to n. It is simple, but it takes n steps.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : List all factors of a number.
 * Input   : One positive integer.
 * Output  : All factors in ascending order on one line.
 * Approach: Test every number from 1 to n.
 * Time    : O(n)
 * Space   : O(k)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long number = new Scanner(System.in).nextLong();
        StringBuilder result = new StringBuilder();

        // Step 1: Try every number from 1 to the number itself.
        for (long divisor = 1; divisor <= number; divisor++) {
            // Step 2: If the number divides without remainder, it is a factor.
            if (number % divisor == 0) {
                // Step 3: Add the factor to the result. Put one space between factors.
                if (result.length() > 0) {
                    result.append(" ");
                }
                result.append(divisor);
            }
        }

        // Step 4: Print all factors on one line.
        System.out.println(result);
    }
}
Hints (1)
  1. A factor divides the number with remainder 0.