找出 1 到 N 之间互为镜像的素数

Question

我遇到了一个问题，我需要找到 1 到 N 范围内素数的镜像。镜像就像 13 和 31、17 和 71 等。我把解决方案写在下面，

    /*
     * find prime numbers within 1 to N that is a mirror to each other
     */
    public static List<Integer> solution(int N) {

        List<Integer> primes = findPrimes(N);
        Set<Integer> set = new LinkedHashSet<>();

        for (int i = 0; i < primes.size(); i++) {

            int prime = primes.get(i);
            int mirror = hasMirror(prime, primes);

            if (mirror == 0) {
                continue;
            }

            set.add(prime);
            set.add(mirror);
        }

        return new ArrayList<>(set);
    }


    /*
     * find the mirror of a number
     * */
    private static int findMirror(int P) {

        int R = 0;

        while (P != 0) {

            int D = P % 10;
            R = R * 10 + D;
            P /= 10;
        }

        return R;
    }

    private static int hasMirror(int P, List<Integer> B) {

        Integer[] A = B.toArray(new Integer[0]);

        int N = A.length;
        int R = findMirror(P);

        for (int i = N - 1; i >= 0; i--) {

            if (A[i] == R) {
                return R;
            }
        }

        return 0;
    }


    public static List<Integer> findPrimes(int N) {

        int[] F = new int[N + 1];
        List<Integer> result = new ArrayList<>();

        for (int i = 2; i <= N; i++) {

            if (F[i] == 0) {

                // the prime value need to be 2 digit for the mirror image
                if (i < 10 || i == findMirror(i)) {
                    continue;
                }

                result.add(i);

                for (int k = i * i; k <= N; k += i) {

                    if (F[k] == 0) {
                        F[k] = 1;
                    }
                }
            }
        }

        return result;
    }
    }

该解决方案有效，但是，是否有提高性能的选项？

Answer 1

提高性能可以做的一件事是，不为已识别的镜像调用 hasMirror()。例如，假设您检查了 17 并确定它有一个镜像 71。然后，当您稍后在循环中到达 71 时，您可以跳过检查它的镜像，因为您已经确定了它。

    List<Integer> primes = findPrimes(N);
    Set<Integer> set = new LinkedHashSet<>();

    for (int i = 0; i < primes.size(); i++) {

        int prime = primes.get(i);

        if (!set.contains(prime)) {
            int mirror = hasMirror(prime, primes);

            if (mirror == 0) {
                continue;
            }

            set.add(prime);
            set.add(mirror);
        }
    }

找出 1 到 N 之间互为镜像的素数

find prime numbers within 1 to N that are mirror to each other

java

primes