нахождение всех простых чисел в заданном диапазоне

Я пишу эту Java-программу, которая находит все простые числа в заданном диапазоне. Поскольку я имею дело с действительно большими числами, мой код кажется недостаточно быстрым и дает мне ошибку времени. Вот мой код, кто-нибудь знает, как сделать его быстрее? Спасибо.

import java.util.*;
public class primes2 
{   
    private static Scanner streamReader = new Scanner(System.in);
    public static void main(String[] args)
    {
        int xrange = streamReader.nextInt(); 
        int zrange = streamReader.nextInt();
        for (int checks = xrange; checks <= zrange; checks++)
        {
            boolean[] checkForPrime = Primes(1000000);
            if (checkForPrime[checks])
            {
                System.out.println(checks);
            }
        }
    }
    public static boolean[] Primes(int n)
    {
        boolean[] isPrime = new boolean[n + 1];
        if (n >= 2)
            isPrime[2] = true;
        for (int i = 3; i <= n; i += 2)
            isPrime[i] = true;
        for (int i = 3, end = sqrt(n); i <= end; i += 2)
        {
            if (isPrime[i]) 
            {
                for (int j = i * 3; j <= n; j += i << 1)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }
    public static int sqrt(int x)
    {
        int y = 0;
        for (int i = 15; i >= 0; i--) 
        {
            y |= 1 << i;
            if (y > 46340 || y * y > x)
                y ^= 1 << i;
        }
        return y;
        }
}

java primes sieve-of-eratosthenes
person Daniel Cook    schedule 24.02.2012    source источник
comment
обратите внимание, что в соответствии с соглашениями об именах в Java имя метода должно быть глаголом и начинаться с нижнего регистра. Итак, что-то вроде findPrimes() — лучшее имя для вашего метода.   -  person amit    schedule 25.02.2012

Ответы (3)


arrow_upward
7
arrow_downward

Вы получите огромное улучшение, просто изменив это:

    for (int checks = xrange; checks <= zrange; checks++)
    {
        boolean[] checkForPrime = Primes(1000000);

к этому:

    boolean[] checkForPrime = Primes(1000000);
    for (int checks = xrange; checks <= zrange; checks++)
    {

Ваш текущий код регенерирует сито zrange - xrange + 1 раза, но на самом деле вам нужно сгенерировать его только один раз.

person ruakh    schedule 24.02.2012

arrow_upward
0
arrow_downward

Очевидная проблема заключается в том, что вы многократно вычисляете простые числа до 1000000 (zrange - xrange раз). Во-вторых, вам не нужно вычислять простые числа до 1000000, вам просто нужно проверить, чтобы простые числа были до zrange, поэтому вы тратите время, когда zrange ‹ 1000000, и получаете переполнение буфера, когда zrange> 1000000.

person Alexander Corwin    schedule 24.02.2012

arrow_upward
0
arrow_downward

Вы можете начать свой внутренний цикл с i*i, т.е. вместо for (int j = i * 3; j <= n; j += i << 1) вы можете написать for (int j = i * i; j <= n; j += i << 1) для небольшого ускорения.

Кроме того, вы должны быть уверены, что ваш zrange не превышает 1000000.

Если xrange намного больше, чем sqrt(zrange), вы также можете разделить массив сита на две части для схемы смещенного сита. Нижний массив будет охватывать диапазон от 2 до sqrt(zrange). Верхний будет охватывать диапазон от xrange до zrange. Когда вы просеиваете свой нижний массив, поскольку каждое новое простое число идентифицируется им, внутри вашего внутреннего цикла, в дополнение к маркировке нижнего массива до его конца, также просеивайте верхний массив. Вам нужно будет вычислить начальное смещение для каждого простого числа i и использовать тот же шаг 2*i, что и для младшей половины. Если ваш диапазон шире, чем несколько простых чисел, вы получите преимущество в скорости (в противном случае будет достаточно просто пробного деления на коэффициенты).

Еще одна вещь, которую стоит попробовать: если четные числа > 2 все равно не являются простыми, зачем представлять их в массиве и тратить половину пространства? Вы можете рассматривать каждый i как представляющий нечетное число, 2*i+1, тем самым сжимая ваш массив пополам.

Последний простой трюк состоит в том, чтобы исключить кратные 3 заранее, пометив ON не только odds (т. е. взаимно простое с 2), { ... i+=2; ...}, но только взаимно простое с 2 и 3 вместо { ... i+=2; ... i+=4; ... }. Кроме того, при маркировке OFF кратных простых чисел > 3 также используйте { ... j+=2*i; ... j+=4i; ...}. Например, в 5*5, 5*7, 5*9, 5*11, ... вам не нужно отмечать OFF 5*9, если ни одно число, кратное 3, не было отмечено ON в первую очередь.

person Will Ness    schedule 27.02.2012