Этот ответ разделен на 2 части: ваш главный решатель (сито чисел) и массив, содержащий ваши числа.
Solver:
Основная область оптимизации, на которой вам нужно сосредоточиться, - это «решетка чисел». Это метод, с помощью которого вы сами определяете, что число простое. В настоящее время невозможно превратить ваше сито в одно выражение, чтобы определить, является ли оно простым, поэтому вы должны стремиться к быстрому устранению. Причина этого в том, что деление и умножение - две самые дорогие арифметические функции, которые вы можете выполнять. Устранение необходимости делать это везде, где это возможно, сэкономит вам больше всего времени. Ниже приведены некоторые основные правила простых чисел (некоторые могут показаться очевидными).
- Число не может быть простым, если оно четное (делится на 2). Самый быстрый способ проверить это:
if ((i && 1) == 1) //prime candidate
- Число является простым, если оно не делится на любые предыдущие простые числа. Другими словами, вам нужно только проверить, используя простые числа, которые вы уже нашли.
for (currentPrime in listOfPrimes) {
if (i mod currentPrime == 0) {
//not Prime: Exit For loop
}
}
- Вам нужно только проверить предыдущие простые числа на 1/3 от текущего i, который вы проверяете (вы уже удалили делится на 2)
- Конечно, есть и другие небольшие оптимизации, но это основная их часть (в настоящее время). Вот скорректированная петля сверху.
if ((i && 1) == 1) {
threshHold = (int)(i / 3); //So you don't have to keep recalcing
isPrime = true; //Assume true until told otherwise
for (currentPrime in listOfPrimes) {
if ((i mod currentPrime) == 0) {
isPrime = false; //Flag as non prime
break; //Exit For Loop early
}
if (currentPrime > threshHold) {
break;
}
}
if (isPrime) {
//Record new Prime
}
}
ArrayList:
Что касается вашего ArrayList, самый эффективный способ оптимизировать это - не хранить ненужную вам информацию. Поскольку (согласно вашему описанию) вы ищете простые, а не простые числа, хранение логического ArrayList для определения, является ли оно простым, не является вашей лучшей ставкой.
Было бы гораздо эффективнее хранить только те простые числа, которые вы найдете, поскольку все, что отсутствует в списке, определенно не является простым. В конце концов, число либо простое, либо нет, поэтому если в списке это простое число, а если нет, то это не так. Это особенно верно, так как ваше числовое сито должно проверяться только против предварительно определенных простых чисел. Это приводит к меньшему количеству записей в ArrayList и меньшему количеству элементов в целом. Кроме того, ваш принудительный вывод о хранении только простых чисел делает ваше логическое значение всегда равным истинному значению, то есть нет необходимости проверять его.
Моя рекомендация такова: измените ваш ArrayList на целое (или длинное) и используйте его как для проверки, так и для вывода, поскольку он служит обеим целям. Существует ряд эффективных способов настроить ваш вывод на основе этого, поэтому это никоим образом не ограничивает вас. Дополнительные функции, позволяющие определить, является ли данное число простым (с учетом вашего списка), - это просто, даже учитывая ArrayList.
FuzzicalLogic