Нахождение простых чисел с Решетом Эратосфена (Первоначально: существует ли лучший способ подготовить этот массив?)
Как насчет этого:
state = {
id_evaluation: 1,
};
const id_eval = getEvaluation();
this.setState({
id_evaluation: id_eval,
});
8 ответов
Ваш метод нахождения начал, путем сравнения каждого элемента массива с каждым возможным фактором ужасно неэффективен. Можно улучшить его очень путем выполнения Решето Эратосфена по целому массиву сразу. Помимо выполнения гораздо меньшего количества сравнений, это также использует дополнение, а не разделение. Подразделение является путем медленнее.
Реструктурируйте свой код. Выведите временный массив и вместо этого запишите функцию что просто главные тесты целое число. Это будет довольно быстро, так как Вы только используете собственные типы. Тогда можно, например, циклично выполнить и создать список целых чисел, которые являются главными, прежде наконец преобразовать это в массив для возврата.
Теперь, когда у Вас есть основное решето на месте, обратите внимание, что внутренний цикл должен только продолжиться до temp[i]*temp[i] > prime.
Вы используете Java 1.5? Почему бы не возвратиться List<Integer> и использование ArrayList<Integer>? Если действительно необходимо возвратиться int[], можно сделать это путем преобразования Списка в int[] в конце обработки.
Самое легкое решение состояло бы в том, чтобы возвратить некоторого члена эти Платформа Наборов вместо массива.
Создайте ArrayList<Integer> и затем преобразуйте в int[] в конце.
существует различная третья сторона IntList (и т.д.) классы вокруг, но если Вы не действительно взволнованы по поводу хита упаковки нескольких целых чисел, я не волновался бы об этом.
Вы могли использовать Arrays.copyOf для создания нового массива все же. Вы могли бы также хотеть изменить размеры путем удвоения в размере каждый раз, когда Вы должны и затем обрезаете в конце. Это в основном имитировало бы ArrayList поведение.
ArrayList<> Решето Эратосфена
// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
final int numPrimes = countPrimesUpperBound(limit);
ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
boolean [] isComposite = new boolean [limit]; // all false
final int sqrtLimit = (int)Math.sqrt(limit); // floor
for (int i = 2; i <= sqrtLimit; i++) {
if (!isComposite [i]) {
primes.add(i);
for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
isComposite [j] = true;
}
}
for (int i = sqrtLimit + 1; i < limit; i++)
if (!isComposite [i])
primes.add(i);
return primes;
}
Формула для верхней границы количества начал, меньше чем или равных max (см. wolfram.com ):
static int countPrimesUpperBound(int max) {
return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}
Как Paul Tomblin указывает, существуют лучшие алгоритмы.
, Но остающийся с тем, что Вы имеете, и принятие объекта на результат является слишком большим:
Вы только когда-либо добавляете к массиву. Так, используйте относительно маленький интервал [] массив. Когда это - использование в полной мере, добавляют его к Списку и создают замену. В конце копируют его в правильно размерный массив.
, С другой стороны, предполагают размер интервала [] массив. Если это является слишком маленьким, замена интервалом [] с размером часть, больше, чем размер современного массива. Производительность наверху этого останется пропорциональной размеру. (Это было обсуждено кратко в недавнем stackoverflow подкасте.)