[Java] Cache all seen prime numbers
Intuition\n Describe your first thoughts on how to solve this problem. \nJust check every pair with cache.\n\n# Approach\n Describe your approach to solving the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nJust check every pair with cache.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCache all prime numbers in the static field.\n\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  // [seen, prime]\n  private static final boolean[][] mark = new boolean[1000000][2];\n\n  public List<List<Integer>> findPrimePairs(int n) {\n    List<List<Integer>> result = new ArrayList<>();\n    for (int i = 2; i <= n - 2 && i <= n - i; i++) {\n      if (!mark[i][0]) {\n        mark[i][0] = true;\n        mark[i][1] = prime(i);\n      }\n\n      if (!mark[n - i][0]) {\n        mark[n - i][0] = true;\n        mark[n - i][1] = prime(n - i);\n      }\n\n      if (mark[i][1] && mark[n - i][1]) {\n        result.add(List.of(i, n - i));\n      }\n    }\n\n    return result;\n  }\n\n  private boolean prime(int n) {\n    for (int i = 2; i * i <= n; i++) {\n      if (n % i == 0) {\n        return false;\n      }\n    }\n    return true;\n  }\n}\n```
['Math', 'Java']