Проблема состоит в том, чтобы создать простое число между двумя интервалами, проблема детализации дана в этой ссылке SPOJ Prime Generator .
Позвольте мне объяснить магические числа и алгоритм, которым я следовал.
Я использовал для реализации модифицированный алгоритм Sieve Eratosthenes (модифицированный в том смысле, что я использовал основную идею).
- Начальный номер интервала, m и Конечный номер интервала n равны <= 10 ^ 9, а разница <strong> равна <= 10 ^ 5 ( 1 <= m <= n <= 1000000000, нм <= 100000) </li>
- Нет четного простого числа, кроме 2, поэтому я рассмотрел max m и n (10 ^ 9) / 2
и sqrt (максимальное число) составляет около 32000 (с учетом нечетных и четных), наконец, 32000/2 = 16 000 - это размер списка нечетных чисел input_aray .
- Наконец, общий диапазон номеров делится на 3 области.
- m и n оба> = 32000 в этом случае размер input_aray равен (n-m + 1) / 2 от индекса 16001 массив, числа между m и n сохраняются (только нечетные числа).
- м и n <32000 </strong>, в этом случае размер input_aray равен n / 2.
- m <32000 и n> 32000 , в этом случае размер input_aray равен (n-32000 + 1) / 2 .
Булево массив бол того же размера, что и input_aray сохраняется для отслеживания того, какое число посещено, так что два числа не могут рассматриваться дважды .
for (int j = 1; j < 16001; j++) {
int flag = input_aray[j];
Этот цикл выбирает n index из input_aray и проверяет, есть ли какое-либо число в этом массиве, которое делится, если это так, то тот же индекс bol инициализируется как false.
for (int k = j + flag; k <= 16000; k = k + flag)
Этот цикл проверяет простые числа до 32000.
for (int k = 16001; k < input_aray.length; k++)
Это проверка между ** m и n ** (когда m & n> = 32000)
* Это самый быстрый подход, который я мог бы реализовать, но все же получил ограничение по времени, превышенное . Что может быть вероятной причиной?
public static void main(String args[]){
Scanner take= new Scanner(System.in);
ArrayList<String> arrayList= new ArrayList<>();
int m,n;
int temp= take.nextInt();
take.nextLine();
if(temp>=0 && temp<=10){
for(int i=0;i<temp;i++) {
String temp1 = take.nextLine();
arrayList.add(temp1);
}
}
for(int i=0;i<arrayList.size();i++){
String[] temp_aray= arrayList.get(i).split(" ");
m= Integer.parseInt(temp_aray[0]);
n= Integer.parseInt(temp_aray[1]);
if(m>0 && n>0 && m<=10E8 && n<=10E8 && n-m<= 10E4 ) {
if (m >= 32000 && n >= 32000) {
//m & n > 32000
int start;
int[] input_aray = new int[16001 + ((n - m + 1) / 2) + 1];
boolean[] bol = new boolean[16001 + ((n - m + 1) / 2) + 1];
Arrays.fill(bol, true);
input_aray[0] = 2;
input_aray[1] = 3;
for (int j = 2; j < 16001; j++) {
input_aray[j] = input_aray[j - 1] + 2;
}
if (m % 2 == 0) {
start = m + 1;
} else {
start = m;
}
for (int j = 16001; j < input_aray.length; j++) {
input_aray[j] = start;
start += 2;
}
for (int j = 1; j < 16001; j++) {
int flag = input_aray[j];
for (int k = j + flag; k <= 16000; k = k + flag) {
if (input_aray[k] % flag == 0 && bol[k] == true) {
bol[k] = false;
}
}
for (int k = 16001; k < input_aray.length; k++) {
if (input_aray[k] % flag == 0) {
bol[k] = false;
}
}
}
int num = 1;
for (int j = 16001; j < bol.length; j++) {
if (bol[j] == true) {
System.out.println(input_aray[j]);
num++;
}
}
System.out.println();
}
if(m<32000 && n< 32000){
int[] input_aray = new int[(n/2)+1];
boolean[] bol = new boolean[(n/2)+1];
Arrays.fill(bol, true);
input_aray[0] = 2;
input_aray[1] = 3;
for (int j = 2; j < input_aray.length; j++) {
input_aray[j] = input_aray[j - 1] + 2;
}
for (int j = 1; j < Math.sqrt(n); j++) {
int flag = input_aray[j];
for (int k = j + flag; k<input_aray.length; k = k + flag) {
if (input_aray[k] % flag == 0 && bol[k] == true) {
bol[k] = false;
}
}
}
int num = 1;
for (int j = 0; j < bol.length; j++) {
if (bol[j] == true && input_aray[j] >=m && input_aray[j]<=n) {
System.out.println(input_aray[j]);
num++;
}
}
System.out.println();
}
if(m<32000 && n>32000){
int start;
int[] input_aray = new int[16001 + ((n - 32000 + 1) / 2) + 1];
boolean[] bol = new boolean[16001 + ((n - 32000 + 1) / 2) + 1];
Arrays.fill(bol, true);
input_aray[0] = 2;
input_aray[1] = 3;
for (int j = 2; j < 16001; j++) {
input_aray[j] = input_aray[j - 1] + 2;
}
start=32001;
for (int j = 16001; j < input_aray.length; j++) {
input_aray[j] = start;
start += 2;
}
for (int j = 1; j < 16001; j++) {
int flag = input_aray[j];
for (int k = j + flag; k <= 16000; k = k + flag) {
if (input_aray[k] % flag == 0 && bol[k] == true) {
bol[k] = false;
}
}
for (int k = 16001; k < input_aray.length; k++) {
if (input_aray[k] % flag == 0) {
bol[k] = false;
}
}
}
int num = 1;
for (int j = 0; j < bol.length; j++) {
if (bol[j] == true && input_aray[j]>=m && input_aray[j]<=n) {
System.out.println(input_aray[j]);
num++;
}
}
System.out.println();
}
}
}
}