Блог

Это мой код для простой генерации:

 import java.io.BufferedReader;
import java.io.InputStreamReader;
public class prime_gen
{

public static void gen_prime(long min,long max)
{

   long n=max/2,i=0,j=0;

        boolean[] prime = new boolean[(int) max];        
 if(min==1)
{

System.out.println("2");
System.out.println("3");

}
else
if(min==3)
System.out.println("3");
else
if(min==2)
{
System.out.println("2");
System.out.println("3");
}

        for (i = 1; i < n; i  )
            for (j = i; j <= (n - i) / (2 * i   1); j  )
                prime[(int) (i   j   2 * i * j)] = true;


for (i = 2; i < prime.length/2; i  )
        {
              if (!prime[(int)i])
                  {
                        if(2*i 1>min)

              System.out.println((2*i 1) " ");
       }






}
}

public static void main(String args[]) 
{
try
{
int i=0,T=0;
long[] min,max;
String[] s1=new String[2];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
T=Integer.parseInt(s);
min=new long[T];
max=new long[T];

for(i=0;i<T;i  )
{
s1=br.readLine().split(" ");
min[i]=Integer.parseInt(s1[0]);
max[i]=Integer.parseInt(s1[1]);



}

for(i=0;i<T;i  )
{
gen_prime(min[i],max[i]);
System.out.println();
}
}catch(Exception e)
{
return;

}   }

}
  

Ограничения заключаются в:

 T<=10
max<=1000000000
max-min<=100000
  

Я использую сито sundaram для генерации простых чисел, и код отлично работает для моих тестовых случаев.Я также использовал блок try catch для обработки исключений.Я не знаю, что не так в этом коде.На форуме spoj говорится, что ошибка NZEC выдается всякий раз, когда JVM генерирует исключение.

приведенный выше код отлично работает при меньшем вводе, но вы проверили, corner or extreme cases с чем имеете дело??когда вы проверите это с помощью extreme cases вы обнаружите, что ваш код выдает runtime error для них .. попробуйте это на ideone, вы получите ошибку времени выполнения .. теперь, в чем проблема для этого?? подумайте об одном тестовом примере, где у нас есть входные данные

999900000 1000000000

теперь в соответствии с вашим кодом

 n = max / 2 = 1000000000 / 2 = 500000000
  

теперь непосредственно переходим к вашему for loop

 for (i = 1; i < n; i  )
        for (j = i; j <= (n - i) / (2 * i   1); j  )
            prime[(int) (i   j   2 * i * j)] = true;
  

учитывая последнее значение (всегда думайте об экстремумах) для внешнего цикла, когда

 i = 500000000 (although `i` will be 1 less than this value ,I am considering it for simplicity as it will have not considerable effect and make our calculations easier)
j = i
  

теперь индекс, который вы обрабатываете для prime массива, теперь соответствует первому значению j

 prime[(int) (i   j   2 * i * j)] = 500000000   some positive number
  

размер массива в любом языке программирования не такой большой (я не знаю о JAVA) .. его примерно 10^6 maximum (может быть больше в JAVA) .. таким образом, вы получаете доступ к индексу, которым нельзя управлять .. вот почему вы получаете runtime error .. вы должны изменить свой подход..

теперь еще одна вещь, на которую я укажу, — это сложность Sieve of Sundaram , которая

O(n * log n)

в то время как Sieve of Eratosthenes имеет сложность

O(n * log(журнал n))

Поэтому я думаю, что вам следует использовать, Sieve of Eratosthenes потому что Sieve of Sundaram это может привести к TLE ..Но Sieve of Eratosthenes этого будет не только достаточно..вы должны использовать segmented sieve для решения этой проблемы .. могут быть и другие методы, с помощью которых вы сможете решить эту проблему.

ПРАВКА 1: — не выходя за рамки, которые вы использовали

 boolean[] prime = new boolean[(int) max];
  

в приведенной выше строке, только как только вы введете упомянутый мной тестовый пример, вы получите runtime error поскольку создание такого большого массива не разрешено на coding websites

ПРАВКА 2: — Я запустил простой код для определения того, возможно ли иметь столько памяти для массива, но я так не думаю .. вот код

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        long max = 1000000000;
        boolean[] prime = new boolean[(int) max];
        System.out.println("IT WORKED");
    }
}
  

и вот что я получил

 Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Ideone.main(Main.java:13)
  

и ссылка на код .. ошибка из-за 10 ^ 9 размера массива