Каково было бы решение этого вопроса, если бы у него были сильные контрольные примеры?

Question

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

Если вы не хотите открывать ссылку, вот краткое описание вопроса ниже:

Эта проблема просит нас напечатать все простые числа в заданном диапазоне.Есть 10 тестовых случаев, и каждый из них предоставит нам начальное и конечное значение диапазона.Начало и конец этого диапазона могут принимать значения от 1 до 10 ^ 9.Разница между начальным и конечным значениями составляет 10 ^ 5 или меньше.Время на решение проблемы составляет 2 секунды.(то есть для всех 10 тестовых случаев вместе)

Я думаю об этом:

Общая оценка состоит в том, что онлайн-судья, используемый Codechef, может выполнить ~ 10 ^ 7 операций за 1 секунду.У нас есть 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 of Eratosthene.Основная предпосылка 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));
}