java - 如果有强大的测试用例，这个问题的解决方案是什么？

Question

https://www.codechef.com/problems/PRIME1

如果您不想打开链接，请在下面对问题进行简短描述:

这个问题要求我们打印给定范围内的所有质数。 有 10 个测试用例，每个测试用例都会为我们提供一个范围的开始值和结束值。 此范围的起点和终点可以取 1 到 10^9 之间的值。 开始值和结束值之间的差异为 10^5 或更小。 该问题的时间限制为 2 秒。 (也就是说，对于所有 10 个测试用例)

我对此的看法:

一个常见的估计是 Codechef 使用的在线判断可以在 1 秒内执行 ~10^7 操作。 我们有 10 个测试用例，在最坏的情况下，每个测试用例的范围都是 10^5(因为这是给定的最大范围)。现在， 10*(10^5)= 10^6 ，这是我们在 1 秒内可以执行的最大操作数，因此对于范围内的每个数字，我们必须在 O(1) 中确定它是否为素数。

Approaches:

1. Simple method for testing primality - Iterate through all numbers from 2 to n-1 and for every number check if it divides n
Ans: Won't work because for the worst case,
= (numbers of the highest size) * (total numbers in max range) * (total test cases)
= (10^9 * 10^5) * 10
= 10^15

2. Square root method to check if prime
Ans: Won't work because, in the worst case,
= (calculating sq. root of numbers of size 10^9) * (total numbers in max range) * (total test cases)
= (~10^4) * (10^5) * 10
= 10^10

3. Using Sieve of Eratosthenes
Precompute primes from 1 to 32000 (this number because it is approx the sq. root of 10^9)
Then to check of a value within the range is primeor not-
if value is between 1 and 32000
    directly refer the precomputed value
else
    try dividing that value by all precomputed primes, if it divides evenly then its not a prime
Ans: won't work  because, in the worst case,
= (number of primes between 1 and 32000) *(total numbers in max range) * (total test cases)
= (3234) * (10^5)  * (10)
= 10^9

方法 3 的代码:

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

class Main
{
    static ArrayList<Integer> sieve(ArrayList<Integer> primes)
    {
        int[] prime=new int[32001];
        for(int i=2; i<32001; i++)
        {
            if(prime[i]==0)
            {
                for(int j=i+i; j<32001; j+=i)
                {
                    prime[j]=1;
                }
            }
        }

        for(int i=2; i<32001; i++)
        {
            if(prime[i]==0)
            {
                primes.add(i);
            }
        }

        return primes;
    }

    public static void main(String[] args)
    {
        int t,m,n,flag;
        ArrayList<Integer> primes= new ArrayList<Integer>();
        FastReader scanner= new FastReader();
        t=scanner.nextInt();
        primes= sieve(primes);
        while(t-- > 0)
        {
            m=scanner.nextInt();
            n=scanner.nextInt();

            for(int i=m; i<=n; i++)
            {
                if(i < 32001)
                {
                    if(primes.contains(i))
                    {
                        System.out.println(i);
                    }
                }
                else
                {
                    flag=0;
                    for(int j=0; j<primes.size(); j++)
                    {
                        if(i%primes.get(j) == 0)
                        {
                            flag=1;
                            break;
                        }
                    }

                    if(flag==0)
                    {
                        System.out.println(i);
                    }
                }
            }

            System.out.println();
        }
    }
}

虽然方法 1 显然行不通，但方法 2 和 3 却出人意料地通过了! 我猜它通过了，因为问题的测试用例很弱。 一个强大的测试用例应该是这样的:

10
999900000 1000000000
999899999 999999999
999899998 999999998
999899997 999999997
999899996 999999996
999899995 999999995
999899994 999999994
999899993 999999993
999899992 999999992
999899991 999999991

我为这个测试用例运行了方法 3，它的计算时间总是超过 2 秒。 如果这个问题确实有强大的测试用例，那么在给定的约束条件下解决它的正确方法是什么？

Answer 1

如果您要尝试找出某个范围内的素数，请使用埃拉托色尼筛法算法。 Sieve 的基本前提是给出一个数字范围，您可以消除所有素数倍数的数字(即一旦我们确定 2 是素数，我们就消除所有它的倍数 ...4、6、8 等)

这个的实现如下:

private void printPrimes(int max) {
   int [] prime = new int[max + 1];
   for (int i = 1; i <= max; i++) {
       prime[i] = i; // Assume everything is prime initially
   }

   // if number is prime, then  multiples of that factor are not prime
   for (int f = 2; f * f <= max; f++) {
       if (prime[f] != 0) {
           for (int j = f; f * j <= max; j++) {
               prime[f * j] = 0;
           }
       }
   }

   int counter = 0;
   for (int i = 1; i <= max; i++) {
       if (prime[i] != 0) counter++;
   }

   prime = Arrays.stream(prime).filter(i -> i != 0).toArray();
   System.out.println("There are " + counter + " primes between 1 and " + max);
   System.out.println(Arrays.toString(prime));
}