Original Problem


  • The idea here is to loop through the elements between l and r (inclusive)
  • For each Integer (整数) we loop through, let it be j
  • Then we Find Minimal Greater-than-One Factor, and let it be md if we can obtain one, and it will be a
  • Then j-md will be b
  • Then GCD of md and j-md will be md which is guaranteed to be >1

Space & Time Analysis

The analysis method we are using is Algorithm Complexity Analysis

Space - O(1)

  • Ignore input size & language dependent space
  • We aren’t creating any objects on the Heap Segment

Time - O(nlogn)


1st Attempt (Java)

import java.util.Scanner;
public class Solution {
  public static void main(String[] args) {
    // Read input data
    Scanner scanner = new Scanner(System.in);
    int t = scanner.nextInt();
    // Loop through the test cases
    for (int i=0; i<t; i++) {
      int l = scanner.nextInt();
      int r = scanner.nextInt();
      boolean found = false;
      for (int j=l; j<=r; j++) {
        int md = minFactor(j);
        // factor means (n-md)%md == 0
        // When the md is >= 2 and md != j and (n-md)%md == 0,  
        // gcd((n-md), md) == md which is guaranteed to be > 1
        if (md != j) {
          found = true;
          System.out.println(md + " " + (j-md));
      if (!found) System.out.println(-1);
  // Time Complexity - O(sqrt(n)), where n is the size of the integer
  public static int minFactor(int n) {
    for (int i=2; i<=Math.sqrt(n); i++) {
      if (n%i == 0) return i;
    // When we cant find factor that is bigger than 2 and smaller than n
    return n;

Personal Reflection

  • Why it takes so long to solve: Unaware of the Find Minimal Greater-than-One Factor
  • What you could have done better: Practice more questions on Number Theory
  • What you missed: Find Minimal Greater-than-One Factor. And an Integer (整数) can be minused all the way to 0 by minusing it with one of its factor after certain number of times
  • Ideas you’ve seen before: Prime Number (质数) and GCD
  • Ideas you found here that could help you later: Find Minimal Greater-than-One Factor in O(logn)
  • Ideas that didn’t work and why: Trying to apply GCD concepts on the potential numbers in the range of l and r, but stuck on how to split the potential number a+b into 2 valid Integer (整数), way to complicated and time consuming. We should think about how to find the 2 valid Integer (整数) from all the potential pair of factors that sum up to the potential number a+b