在 {1, ..., n} 中找出最后一位为 7 的最大质数

Question

假设n 是一个250000 左右的整数。使用Java，我需要找到以7 结尾且属于{1, ..., n} 的最大质数。此外，我需要关注计算复杂性并尽可能降低它。所以我在考虑对 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;
}

我想这会让整个事情变得简单，但我想知道更有效的方法是什么。除非有一种方法可以轻松避免使用数组，但我想不出任何方法。

Answer 1

在下面，您将看到我实现的用于查找 1 到 250000 之间的素数的埃拉托色尼筛法算法，以及我如何使用它来过滤掉所有以 7 结尾的素数。

该算法的总体时间复杂度为 O(N)，因为所有实现都是在筛选算法中完成的。

    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中作为非质数被覆盖，i达到7的事实证明它是一个素数，所以我保留一个全局数组列表作为我的数据结构，只添加那些以 7 结尾的素数，因为我使用 % 运算符来计算数字的最后一位，所以该步骤的时间复杂度是 O(1 ), 所以算法的总时间复杂度为 O(N).

让我知道，如果我在算法中有任何错误，我会改正。

希望对您有所帮助！

在 {1, ..., n} 中找出最后一位为 7 的最大质数

Find the greatest prime number with 7 as the last digit in {1, ..., n}

algorithm

primes

time-complexity