algorithm - 在{1，…，n}中找到以7作为最后一位的最大质数

假设n是一个大约250000的整数。使用Java，我需要找到以7结尾且属于{1，…，n}的最大素数此外，我需要关注计算复杂性，并尽量降低它。
所以我想用Eratosthenes筛来表示n，然后检查我的bool值数组

int start = (n % 10 < 7 ? n - (n % 10 + 3) : n - (n % 10 - 7) )
    for (int i = start; i >= 0; i-= 10){
        if(primes[i])
            return i;
}

我想这会使整个事情保持简单，但我想知道什么是更有效的方法除非有一种方法可以很容易地避免数组，但我想不出任何方法。

最佳答案

在下面，您将看到我的实现，埃拉托舍内斯筛算法寻找素数在1和250000之间，以及我如何利用它，过滤出所有以7结尾的素数。
该算法的总体时间复杂度为O（n），因为所有的实现都是在筛分ALGO中完成的。

    import java.io.*;
    import java.util.*;

    public class Main {
        public static void main(String[] args) {
            int N = 250000;

            ArrayList<Integer> primeWithEnding7 = new ArrayList<Integer>();
            int maxPrimeNum7 = 0;
            boolean[] isPrime = new boolean[N + 1];
            for (int i = 2; i <= N; i++) {
                isPrime[i] = false;
            }

            for (int i = 2; i <= N; i++) {
                if (!isPrime[i]) {
                    int rem = i%10;
                    if(rem == 7) {
                      maxPrimeNum7 = Math.max(maxPrimeNum7, i);
                      primeWithEnding7.add(i);
                    }
                    for (int j = i+i; j <= N; j+=i) {
                        isPrime[j] = true;
                    }
                }
            }

            // Print all the prime numbers ending in 7
            for(int i: primeWithEnding7) {
              System.out.print(i + " ");
            }
            System.out.println();
            System.out.println("Max number is " + maxPrimeNum7);
      }
    }

现在让我们举一个例子来理解为什么这个算法对我们有效。
假设n=30。现在，当循环从2开始，如果7不是素数，它在内部循环j中会被覆盖为非素数，我达到7的事实证明它是素数，所以我保留一个全局数组列表作为我的数据结构，只添加那些以7结尾的素数，因为我使用%运算符来计算数字的最后一个数字，该步骤的时间复杂度为O（1），因此算法的总时间复杂度为O（n）。
让我知道，如果我在算法上犯了什么错误，我会改正的。
希望这有帮助！