как использовать метод Arraylist для другого метода?

Question

Я должен найти и вернуть k-й элемент в последовательности простых чисел. например, если k = 5, то пятое простое число равно 11. (2, 3, 5, 7, 11, 13, 17, 19, 23 ...). Я также пытаюсь пройти тестер.

Мне удалось создать метод списка и метод kthPrime, но я не понимаю, как их использовать вместе. Мой метод kthPrime очень-очень медленный, когда тестер запускается и дает сбой.

Чтобы ускорить процесс, мы должны использовать Arraylist для хранения последовательности сгенерированных простых чисел (нужно найти в течение 1 минуты).

import java.util.*;
import java.util.ArrayList;

 public class Primes {
  
  public static boolean isPrime(int n) {

    if (n <= 1) 
        return false; 

    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 

    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
            
    return true; 
    
}
    
private static ArrayList<Integer> list(int x) {
    ArrayList list = new ArrayList<String>();
     for (int i = 0 ; i < 100000 ; i++) {
         if(isPrime(i) == true)
         list.add(i);
   }
return list;
}

public static int kthPrime(int k){
int max = 100000000;
int i;
int counter=1;
for (i = 0 ; i <=max ; i++){
    
    if (isPrime(i) == true){
        counter++;
        if(counter > k)
            break;
    }
}
return i;
}


public static void main(String args[]){

    int k;
    Scanner input = new Scanner(System.in);
    System.out.println("Enter k");
    k = input.nextInt();
    System.out.println("kth prime = "+Primes.kthPrime(k));
    System.out.println("primelist = "+Primes.list(k));
   }
  }

Тестер:

 import static org.junit.Assert.*;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;

 import java.io.*;
 import java.util.*;
 import java.util.zip.CRC32;

public class PrimesTest {

@Test public void isPrimeTest() {
    CRC32 check = new CRC32();
    for(int k = 0; k < 10_000_000; k++) {
        if(Primes.isPrime(k)) { check.update(k); }            
    }
    assertEquals(783904569L, check.getValue());
}

@Test public void kthPrimeTest() {
    CRC32 check = new CRC32();
    for(int k = 0; k < 30_000; k++) {
        check.update(Primes.kthPrime(k));
    }
    assertEquals(3080752681L, check.getValue());
   }
 }
  

Answer 1

Вы можете ускорить метод списка, применив алгоритм Sieve of Eratosthene , если позволяет максимальный предел. Проверьте алгоритм отсюда - Сито Эратосфена

 public static ArrayList<Integer> list(int n) { 
    // Create a boolean array & initialize full array as true. 
    // A value in prime[i] will finally be false if i is not a prime, else true.
    boolean prime[] = new boolean[n+1]; 
    for(int i=0;i<n;i++) 
        prime[i] = true; 
    
    for(int p = 2; p*p <=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if(prime[p] == true) 
        { 
            // Update all multiples of p 
            for(int i = p*p; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 
 
    ArrayList list = new ArrayList<Integer>();
    for(int i = 2; i <= n; i++) 
    { 
        if(prime[i] == true) 
            list.add(i);// i is prime 
    }
 
   return list;
}

Answer 2

Простым способом продолжить было бы усовершенствовать метод kthPrime, чтобы он также принимал список известных простых чисел. Если k меньше длины списка, вы можете просто извлечь k-е простое число из списка. Если это не так, вы можете добавлять простые числа в список, пока он не будет иметь длину k, а затем получить последний элемент.