Ответ 1

Вам не нужно добавлять всех возможных кандидатов в массив. Вы можете создать набор для хранения всех не простых чисел.

Также вы можете начать проверку с k * k, а не 2 * k

  public void primesTo1000() {
    Set<Integer> notPrimes = new HashSet<>();
    ArrayList<Integer> primes = new ArrayList<>();
    primes.add(2);//explicitly add
    primes.add(3);//2 and 3

    for (int i = 1; i < (1000 / 6); i++) {
      handlePossiblePrime(6 * i - 1, primes, notPrimes);
      handlePossiblePrime(6 * i + 1, primes, notPrimes);
    }
    System.out.println(primes);
  }

  public void handlePossiblePrime(
      int k, List<Integer> primes, Set<Integer> notPrimes) {
    if (!notPrimes.contains(k)) {
      primes.add(k);
      for (int j = k * k; j <= 1000; j += k) {
        notPrimes.add(j);
      }
    }
  }

непроверенный код, проверка углов

Вот немного упаковочная версия сита, как предложено в ответ, на который ссылается @Wess Ness, Вместо того, чтобы возвращать n _th prime, эта версия возвращает список простых чисел в n:

public List<Integer> primesTo(int n) {
  List<Integer> primes = new ArrayList<>();
  if (n > 1) {
    int limit = (n - 3) >> 1;
    int[] sieve = new int[(limit >> 5) + 1];
    for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
      if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
        int p = i + i + 3;
        for (int j = (p * p - 3) >> 1; j <= limit; j += p)
          sieve[j >> 5] |= 1 << (j & 31);
      }
    primes.add(2);
    for (int i = 0; i <= limit; i++)
      if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
        primes.add(i + i + 3);
  }
  return primes;
}

Кажется, что в вашем обновленном коде есть ошибка, которая использует булевский массив (он не возвращает все простые числа).

public static List<Integer> booleanSieve(int n) {
  boolean[] primes = new boolean[n + 5];
  for (int i = 0; i <= n; i++)
    primes[i] = false;
  primes[2] = primes[3] = true;
  for (int i = 1; i <= n / 6; i++) {
    int prod6k = 6 * i;
    primes[prod6k + 1] = true;
    primes[prod6k - 1] = true;
  }
  for (int i = 0; i <= n; i++) {
    if (primes[i]) {
      int k = i;
      for (int j = k * k; j <= n && j > 0; j += k) {
        primes[j] = false;
      }
    }
  }

  List<Integer> primesList = new ArrayList<>();
  for (int i = 0; i <= n; i++)
    if (primes[i])
      primesList.add(i);

  return primesList;
}

public static List<Integer> bitPacking(int n) {
  List<Integer> primes = new ArrayList<>();
  if (n > 1) {
    int limit = (n - 3) >> 1;
    int[] sieve = new int[(limit >> 5) + 1];
    for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
      if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
        int p = i + i + 3;
        for (int j = (p * p - 3) >> 1; j <= limit; j += p)
          sieve[j >> 5] |= 1 << (j & 31);
      }
    primes.add(2);
    for (int i = 0; i <= limit; i++)
      if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
        primes.add(i + i + 3);
  }
  return primes;
}

public static void main(String... args) {
  Executor executor = Executors.newSingleThreadExecutor();
  executor.execute(() -> {
    for (int i = 0; i < 10; i++) {
      int n = (int) Math.pow(10, i);
      Stopwatch timer = Stopwatch.createUnstarted();
      timer.start();
      List<Integer> result = booleanSieve(n);
      timer.stop();
      System.out.println(result.size() + "\tBoolean: " + timer);
    }

    for (int i = 0; i < 10; i++) {
      int n = (int) Math.pow(10, i);
      Stopwatch timer = Stopwatch.createUnstarted();
      timer.start();
      List<Integer> result = bitPacking(n);
      timer.stop();
      System.out.println(result.size() + "\tBitPacking: " + timer);
    }
  });
}

0   Boolean: 38.51 μs
4   Boolean: 45.77 μs
25  Boolean: 31.56 μs
168 Boolean: 227.1 μs
1229    Boolean: 1.395 ms
9592    Boolean: 4.289 ms
78491   Boolean: 25.96 ms
664116  Boolean: 133.5 ms
5717622 Boolean: 3.216 s
46707218    Boolean: 32.18 s
0   BitPacking: 117.0 μs
4   BitPacking: 11.25 μs
25  BitPacking: 11.53 μs
168 BitPacking: 70.03 μs
1229    BitPacking: 471.8 μs
9592    BitPacking: 3.701 ms
78498   BitPacking: 9.651 ms
664579  BitPacking: 43.43 ms
5761455 BitPacking: 1.483 s
50847534    BitPacking: 17.71 s

Ответ 2

5 - это первое число, сгенерированное по вашим критериям. Посмотрим на числа, созданные до 25:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Теперь рассмотрим эти же числа, когда мы используем алгоритм Сито Эратосфена:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

После удаления 2:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 > , 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

После удаления 3:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Это то же самое, что и первый набор! Обратите внимание, что оба они включают 25, что не является простым. Если мы подумаем об этом, это будет очевидный результат. Рассмотрим любую группу из 6 последовательных чисел:

6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2

Если мы немного затухаем, получим:

3 * (2k - 1), 2 * (3k - 1), 6k - 1, 6 * (k), 6k + 1, 2 * (3k + 1)

В любой группе из 6 последовательных чисел три из них будут делиться на два, а два из них будут делиться на три. Это именно те числа, которые мы удалили до сих пор! Поэтому:

Ваш алгоритм использовать только 6k - 1 и 6k + 1 точно так же, как и первые два раунда сита эрафосфенов.

Это неплохое улучшение скорости по сравнению с ситом, потому что нам не нужно добавлять все эти дополнительные элементы только для их удаления. Это объясняет, почему работает ваш алгоритм и почему он не пропускает никаких случаев; потому что он точно такой же, как сито.

В любом случае, я согласен с тем, что после того, как вы сгенерировали простые числа, ваш boolean способ , безусловно, самый быстрый. Я установил контрольный пример с помощью метода ArrayList, ваш boolean[] и мой собственный путь с использованием LinkedList и iterator.remove() (потому что удаление происходит быстрее в LinkedList. Вот код для моего тестового жгута. Обратите внимание, что я запускаю тест 12 раз, чтобы убедиться, что JVM разогрет, и я печатаю размер списка и изменяю размер n, чтобы предотвратить слишком большую оптимизацию прогнозирования ветвей. Вы также можете ускориться во всех трех методах используя += 6 в начальном семени вместо prod6k:

import java.util.*;

public class PrimeGenerator {
  public static List<Integer> generatePrimesArrayList(int n) {
    List<Integer> primes = new ArrayList<>(getApproximateSize(n));
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      // remove all the factors of the numbers generated by the formula
      for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
                                         // to DTing
      {
        int index = primes.indexOf(j);
        if (index != -1)
          primes.remove(index);
      }
    }
    return primes;
  }

  public static List<Integer> generatePrimesBoolean(int n) {
    boolean[] primes = new boolean[n + 5];
    for (int i = 0; i <= n; i++)
      primes[i] = false;
    primes[2] = primes[3] = true;

    for (int i = 6; i <= n; i+=6) {
      primes[i + 1] = true;
      primes[i - 1] = true;
    }

    for (int i = 0; i <= n; i++) {
      if (primes[i]) {
        int k = i;
        for (int j = k * k; j <= n && j > 0; j += k) {
          primes[j] = false;
        }
      }
    }

    int approximateSize = getApproximateSize(n);
    List<Integer> primesList = new ArrayList<>(approximateSize);
    for (int i = 0; i <= n; i++)
      if (primes[i])
        primesList.add(i);

    return primesList;
  }

  private static int getApproximateSize(int n) {
    // Prime Number Theorem. Round up
    int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
    return approximateSize;
  }

  public static List<Integer> generatePrimesLinkedList(int n) {
    List<Integer> primes = new LinkedList<>();
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
        int primeCandidate = iterator.next();
        if (primeCandidate == k)
          continue; // Always skip yourself
        if (primeCandidate == (primeCandidate / k) * k)
          iterator.remove();
      }
    }
    return primes;
  }

  public static void main(String... args) {
    int initial = 4000;

    for (int i = 0; i < 12; i++) {
      int n = initial * i;
      long start = System.currentTimeMillis();
      List<Integer> result = generatePrimesArrayList(n);
      long seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tArrayList Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesBoolean(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tBoolean Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesLinkedList(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
    }
  }
}

И результаты последних нескольких испытаний:

3432    ArrayList Seconds: 430
3432    Boolean Seconds: 0
3432    LinkedList Seconds: 90
3825    ArrayList Seconds: 538
3824    Boolean Seconds: 0
3824    LinkedList Seconds: 81
4203    ArrayList Seconds: 681
4203    Boolean Seconds: 0
4203    LinkedList Seconds: 100
4579    ArrayList Seconds: 840
4579    Boolean Seconds: 0
4579    LinkedList Seconds: 111

Ответ 3

Есть несколько вещей, которые можно было бы оптимизировать.

Для начала операции "contains" и "removeAll" в ArrayList являются довольно дорогостоящими операциями (линейными для первого, наихудшего квадратичного для последнего), поэтому вы можете не использовать ArrayList для этого. У Hash- или TreeSet есть лучшие сложности для этого, будучи почти постоянными (сложности хеширования странные) и логарифмические, я думаю,

Вы можете заглянуть в решетку решета Эратосфена, если хотите более эффективный сито-альтегометр, но это будет, кроме того, вопрос вашего вопроса об трюке 6k + -1. Это немного, но не заметно больше памяти, чем ваше решение, но быстрее.

Ответ 4

Можно ли оптимизировать этот подход?

Ответ: да.

Начну с того, что неплохо использовать сито для подмножества числа в определенном диапазоне, и ваше предложение делает именно это.

Чтение о генерации Primes:

... Кроме того, на основе формализованных сит, некоторые целые последовательности (последовательность A240673 в OEIS), которые они также может использоваться для генерации простых чисел в определенные интервалы.

Смысл этого параграфа заключается в том, что ваш подход, начинающийся с сокращенного списка целых чисел, действительно был принят академией, но их методы более эффективны (но также, естественно, более сложны).

Ответ 5

Вы можете генерировать свои пробные номера с помощью колеса, добавляя поочередно 2 и 4, что исключает умножение в 6 * k +/- 1.

public void primesTo1000() {
  Set<Integer> notPrimes = new HashSet<>();
  ArrayList<Integer> primes = new ArrayList<>();
  primes.add(2);  //explicitly add
  primes.add(3);  //2 and 3

  int step = 2;
  int num = 5  // 2 and 3 already handled.
  while (num < 1000) {     
    handlePossiblePrime(num, primes, notPrimes);
    num += step;      // Step to next number.
    step = 6 - step;  // Step by 2, 4 alternately.
  }
  System.out.println(primes);
}

Ответ 6

Вероятно, наиболее подходящей стандартной структурой данных для Сита Эратосфена является BitSet. Здесь мое решение:

static BitSet genPrimes(int n) {
    BitSet primes = new BitSet(n);
    primes.set(2); // add 2 explicitly
    primes.set(3); // add 3 explicitly
    for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication
        primes.set(i - 1);
        primes.set(i + 1);
    }
    int max = (int) Math.sqrt(n); // don't need to filter multiples of primes bigger than max

    // this for loop enumerates all set bits starting from 5 till the max
    // sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3
    for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) {
        // The actual sieve algorithm like in your code
        for(int j = i * i; j <= n; j += i)
            primes.clear(j);
    }
    return primes;
}

Использование:

BitSet primes = genPrimes(1000); // generate primes up to 1000
System.out.println(primes.cardinality()); // print number of primes
// print all primes like {2, 3, 5, ...}
System.out.println(primes);
// print all primes one per line
for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1))
    System.out.println(prime);
// print all primes one per line using java 8:
primes.stream().forEach(System.out::println);

Булева версия может работать быстрее при небольших значениях n, но если вам понадобится, например, миллион простых чисел, BitSet будет превосходить ее в несколько раз и фактически работает правильно. Здесь хромой критерий:

public static void main(String... args) {
    long start = System.nanoTime();
    BitSet res = genPrimes(10000000);
    long diff = System.nanoTime() - start;
    System.out.println(res.cardinality() + "\tBitSet Seconds: " + diff / 1e9);

    start = System.nanoTime();
    List<Integer> result = generatePrimesBoolean(10000000); // from durron597 answer
    diff = System.nanoTime() - start;
    System.out.println(result.size() + "\tBoolean Seconds: " + diff / 1e9);
}

Вывод:

664579  BitSet Seconds: 0.065987717
664116  Boolean Seconds: 0.167620323

664579 правильное число простых чисел ниже 10000000.