Это лучший способ найти максимальное количество чисел, с которыми я могу справиться?

Question

Я пытаюсь найти, сколько простых чисел я могу получить, пока продукт из двух больших больше Long.MAX_VALUE.

Это занимает более получаса (и ГЗ ОЗУ)

public class Main { 
    public static void main(String[] args) { 
     ArrayList <Long> primes= new ArrayList<Long>(); 
     primes.add(2L); 
     long i=3L; 
     // Looping from 3, to the limit 
     while (primes.size()<2||(primes.get(primes.size()-1)*primes.get(primes.size()-2)<Long.MAX_VALUE)) {    
      boolean isPrime = true; 
      long maxDiv =Math.round(Math.sqrt(i)); 
      int j=0; 
       while(primes.get(j)<maxDiv && isPrime) { 
       if (i % primes.get(j) == 0) { 
        isPrime = false; 
       } 
       j++; 
      }   
      if (isPrime) { 
       primes.add(i); 
       System.out.println(i); 
      } 
      i=i+2; 
     } 
     System.out.println("max size is: "+primes.size()); 
    } 
} 

EDIT

Я также заинтересован в том, сколько простых чисел я получаю до достижения этого предела. Таким образом, подход сверху вниз не будет выполнять эту работу.

Во всяком случае, я понял, что я смог бы достичь тех двух цифр в моем приложении, я стал бы богат, как ад, в то же время :)

Answer 1

Там должен быть более быстрым способом сделать это. Рассмотрим следующий пример:

• Используйте сито или Эратосфен для чисел между 2 и Sqrt(Long.MAX_VALUE)
• Найти следующий простое число (next) после последнего простого числа (last), найденной решето.
• Если next*last уже больше Long.MAX_VALUE, все готово.
• Если не найти следующий primenumber после next (назовем его next2)
• next*next2 больше, чем Long.MAX_VALUE

решета Эратосфена имеет временную сложность O(n*log(log(n)).

Вам нужно будет только «грубой силы» 2 простых числа, которые больше Sqrt(Long.MAX_VALUE). Добавленный к времени, необходимому для расчета сита, это должно быть значительно быстрее, чем ваш подход!

---

Для того, что вы должны рассчитывать простые числа:

Это очень легко подсчитать количество простых чисел при расчете решето!