Как я могу проверить на первичность?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пишу небольшую библиотеку с некоторыми методами, связанными с простыми числами. Поскольку я сделал основы (или рабочие методы) и теперь я ищу некоторую оптимизацию. Конечно, Интернет является отличным местом для этого. Однако я наткнулся на проблему с округлением, и мне было интересно, как ее решить.
В цикле, который я использую для проверки числа на простоту, поиск более эффективен, пока sqrt (n) вместо n / 2 или даже n - 1. Но из-за проблем с округлением некоторые числа пропускаются, и поэтому некоторые простые числа пропущено! Например, 10000-е простое число должно быть: 104729, но «оптимизированная» версия заканчивается 103811.
Некоторый код (я знаю, он открыт для дополнительной оптимизации, но я могу обрабатывать только одну вещь за раз):
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers
if (test == 0 || test == 1) return false;
// 2 and 3 are prime numbers
if (test == 2) return true;
// all even numbers, save 2, are not prime
if (test % 2 == 0) return false;
double squared = Math.Sqrt(test);
int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
// start with 5, make increments of 2, even numbers do not need to be tested
for (int idx = 3; idx < flooredAndSquared; idx++)
{
if (test % idx == 0)
{
return false;
}
}
return true;
}
Я знаю, что квадратная часть меня не устраивает (или я провалю), пробовал и Math.Ceiling, примерно с теми же результатами.
Решение
К сожалению, я не пробовал алгоритмические подходы раньше. Но если вы хотите эффективно реализовать свой подход, я бы посоветовал заняться кэшированием. Создайте массив для хранения всех простых чисел, меньших определенного порога, заполните этот массив и выполните поиск в нем / используя его.
В следующем примере определение того, является ли число простым, в лучшем случае является O (1) (а именно, когда число меньше или равно maxPrime , что составляет 821 461 для 64 КБ буфер), и несколько оптимизирован для других случаев (проверяя мод только на 64 КБ числах из первых 820 000 - около 8%).
(Примечание. Не принимайте этот ответ как "оптимальный" подход. Это скорее пример того, как оптимизировать реализацию.)
public static class PrimeChecker
{
private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
private static int[] primes;
public static int MaxPrime { get; private set; }
public static bool IsPrime(int value)
{
if (value <= MaxPrime)
{
return Array.BinarySearch(primes, value) >= 0;
}
else
{
return IsPrime(value, primes.Length) && IsLargerPrime(value);
}
}
static PrimeChecker()
{
primes = new int[BufferSize];
primes[0] = 2;
for (int i = 1, x = 3; i < primes.Length; x += 2)
{
if (IsPrime(x, i))
primes[i++] = x;
}
MaxPrime = primes[primes.Length - 1];
}
private static bool IsPrime(int value, int primesLength)
{
for (int i = 0; i < primesLength; ++i)
{
if (value % primes[i] == 0)
return false;
}
return true;
}
private static bool IsLargerPrime(int value)
{
int max = (int)Math.Sqrt(value);
for (int i = MaxPrime + 2; i <= max; i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
}
Другие советы
Я полагаю, это ваша проблема.
for (int idx = 3; idx < flooredAndSquared; idx++)
Это должно быть
for (int idx = 3; idx <= flooredAndSquared; idx++)
так что вы не получите квадратные числа в виде простых чисел. Также вы можете использовать " idx + = 2 " вместо " idx ++ " потому что вам нужно только проверить нечетные числа (как вы написали в комментарии выше ...).
Я не знаю, действительно ли это то, что вы ищете, но если вы действительно беспокоитесь о скорости, то вам следует использовать вероятностные методы тестирования простоты, а не использовать сито. Рабин-Миллер - это вероятностный тест на простоту, используемый Mathematica.
Я разместил класс, который использует сито или Eratosthenes для вычисления простых чисел здесь:
Ограничен ли размер массива верхним пределом int (2147483647)?
Как сказал Марк, тест Миллера-Рабина на самом деле очень хороший путь. Дополнительной ссылкой (с псевдокодом) является статья в Википедии о он.
Следует отметить, что, хотя оно является вероятностным, путем тестирования очень небольшого числа случаев вы можете определить, является ли число простым для чисел в диапазоне int (и почти длинном). См. эту часть этой статьи Википедии или
Я бы также рекомендовал прочитать эту статью о модульном построении, иначе вы собираетесь иметь дело с очень очень большими числами при попытке выполнить тест Миллера-Рабина ...
Возможно, вы захотите взглянуть на небольшую теорему Ферма .
Вот псевдокод из книги Алгоритмы С. Дасгупты, C.H. Пападимитриу и У.В. Вазирани , где n - это число, которое вы проверяете на простоту.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
Реализация теоремы Ферма должна быть быстрее, чем сито. Однако есть числа Кармайкла, которые проходят тест Ферма и НЕ являются простыми. Есть обходные пути для этого. Я рекомендую обратиться в раздел 1.3 вышеупомянутой книги . Это все о тестировании на первичность и может быть полезно для вас.
Попробуйте это ...
if (testVal == 2) return true;
if (testVal % 2 == 0) return false;
for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
if (testVal % i == 0)
return false;
}
return true;
Я использовал это довольно часто ... Не так быстро, как сито ... но это работает.
Вот наполовину достойная функция, которую я написал для решения одной из задач Эйлера:
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
У меня есть быстрый алгоритм проверки простых чисел. Вы можете улучшить свой алгоритм, если знаете, что простые числа имеют вид 6k & # 177; 1, за исключением 2 и 3. Итак, сначала вы можете проверить, делится ли ввод на 2 или 3. Затем проверьте все числа в форме 6k & # 177; 1 & # 8804; & # 8730;. Ввод
bool IsPrime(int input)
{
//2 and 3 are primes
if (input == 2 || input == 3)
return true;
else if (input % 2 == 0 || input % 3 == 0)
return false; //Is divisible by 2 or 3?
else
{
for (int i = 5; i * i <= input; i += 6)
{
if (input % i == 0 || input % (i + 2) == 0)
return false;
}
return true;
}
}
Попробуйте сито с эратосфеном , которое не должно получать корневую и плавающую точку вопросы.
Что касается floor , вам будет лучше обслуживаться, если взять потолок .
private static bool IsPrime(int number) {
if (number <= 3)
return true;
if ((number & 1) == 0)
return false;
int x = (int)Math.Sqrt(number) + 1;
for (int i = 3; i < x; i += 2) {
if ((number % i) == 0)
return false;
}
return true;
}
Я не могу получить это быстрее ...
Я подумал, что тестирование простых чисел и простых чисел был полезен, и алгоритм AKS звучит интересно, даже если он не особенно практичен по сравнению с вероятностными тестами.
Это работает очень быстро для тестирования простых чисел (vb.net)
Dim rnd As New Random()
Const one = 1UL
Function IsPrime(ByVal n As ULong) As Boolean
If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
return false
End If
Dim s = n - one
While s Mod 2 = 0
s >>= one
End While
For i = 0 To 10 - 1
Dim a = CULng(rnd.NextDouble * n + 1)
Dim temp = s
Dim m = Numerics.BigInteger.ModPow(a, s, n)
While temp <> n - one AndAlso m <> one AndAlso m <> n - one
m = (m * m) Mod n
temp = temp * 2UL
End While
If m <> n - one AndAlso temp Mod 2 = 0 Then
Return False
End If
Next i
Return True
End Function
В случае, если кому-то еще интересно, вот мое преобразование описанной выше процедуры Мухаммеда в VBA. Я добавил проверку, чтобы исключить 1, 0 и отрицательные числа, так как все они определены как не простые.
Я только что проверил это в Excel VBA:
Function IsPrime(input_num As Long) As Boolean
Dim i As Long
If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
IsPrime = False: Exit Function
ElseIf input_num = 2 Then
IsPrime = True: Exit Function '2 is a prime
ElseIf input_num = 3 Then
IsPrime = True: Exit Function '3 is a prime.
ElseIf input_num Mod 2 = 0 Then
IsPrime = False: Exit Function 'divisible by 2, so not a prime.
ElseIf input_num Mod 3 = 0 Then
IsPrime = False: Exit Function 'divisible by 3, so not a prime.
Else
'from here on, we only need to check for factors where
'6k ± 1 = square root of input_num:
i = 5
Do While i * i <= input_num
If input_num Mod i = 0 Then
IsPrime = False: Exit Function
ElseIf input_num Mod (i + 2) = 0 Then
IsPrime = False: Exit Function
End If
i = i + 6
Loop
IsPrime = True
End If
End Function
Ваш цикл for должен выглядеть следующим образом:
for (int idx = 3; idx * idx <= test; idx++) { ... }
Таким образом, вы избегаете вычислений с плавающей точкой. Должен бежать быстрее и будет точнее. Вот почему условный оператор for является просто логическим выражением: он делает такие вещи возможными.
