Как я могу протестировать на простоту чисел?
также, длинный метод - это было последнее средство после попытки всех элементов выше:
c:\python27\scripts\pip.exe install [package].whl
это после cd в каталоге, где находится колесо
12 ответов
К сожалению, я не попробовал алгоритмические подходы прежде. Но если бы Вы хотите реализовать свой подход эффективно, я предложил бы делать некоторое кэширование. Создайте массив, чтобы сохранить все простые числа меньше, чем определенный порог, заполнить этот массив и поиск в/использующий нем.
В следующем примере, находя, является ли число простым, O (1) в лучшем случае (а именно, когда число меньше чем или равно maxPrime, который является 821,461 для буфера 64K), и несколько оптимизирован для других случаев (путем проверения модификации только 64K числа из первых 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;
}
}
Попробуйте это...
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;
Ive использовал это довольно много раз.. Не с такой скоростью, как решето.. но это работает.
Ваш для цикла должен быть похожим на это:
for (int idx = 3; idx * idx <= test; idx++) { ... }
Тот путь, Вы избегаете вычисления с плавающей точкой. Должен работать быстрее, и это будет более точно. Поэтому for условное выражение оператора является просто булевым выражением: это делает вещи как это возможными.
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;
}
я не могу получить его немного быстрее...
Попробуйте решето Эратосфена - который должен вынуть получение корневых и проблем с плавающей точкой.
Что касается эти floor, Вы будете лучше обслуживаться путем взятия ceiling.
Вы могли бы хотеть изучить небольшая теорема Fermat .
Вот псевдо код из книги Алгоритмы S. Dasgupta, C.H. Papadimitriou и U.V. Vazirani, где n является числом, Вы тестируете на простоту чисел.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
теорема Fermat Реализации должна быть быстрее тогда решение для решета. Однако существуют числа Carmichael, которые проходят тест Fermat и НЕ являются главными. Существуют обходные решения для этого. Я рекомендую консультироваться , Раздел 1.3 в носу упомянул книгу . Это - все о тестировании простоты чисел и могло бы быть полезно для Вас.
Как Mark сказал, тест Miller-Rabin является на самом деле очень хорошим способом пойти. Дополнительная ссылка (с псевдокодом) статья Wikipedia об этом.
нужно отметить, что, в то время как это вероятностно путем тестирования просто очень небольшого количества случаев, можно определить, является ли число простым для чисел в интервале (и почти долго) диапазон. См. эта часть той статьи Wikipedia, или Доказательство Простоты чисел, ссылочное для получения дополнительной информации.
я также рекомендовал бы читать эта статья о модульном возведении в степень, поскольку иначе Вы собираетесь быть контактом с очень очень большими количествами при попытке сделать тест Miller-Rabin...
Я отправил класс, который использует решето или Eratosthenes для вычисления простых чисел здесь:
размер массива, ограниченного верхним пределом интервала (2147483647)?
Я предполагаю, что это - Ваша проблема:
for (int idx = 3; idx < flooredAndSquared; idx++)
Это должно быть
for (int idx = 3; idx <= flooredAndSquared; idx++)
, таким образом, Вы не получаете квадратные числа как начала. Кроме того, можно использовать "idx + = 2" вместо "idx ++", потому что только необходимо протестировать нечетные числа (как Вы записали в комментарии непосредственно выше...).
Вот промежуточная достойная функция, которую я записал для решения одного из Euler:
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;
}
}
Я не знаю, вполне ли это, что Вы ищете, но если Вы действительно обеспокоены скоростью тогда, необходимо изучить вероятностные методы для тестирования простоты чисел вместо того, чтобы использовать решето. Rabin-Miller является вероятностным тестом простоты чисел, используемым Mathematica.
Я думал, что Простые числа и проверка простоты были полезны, а алгоритм AKS звучит интересно, даже если он не особенно практичен по сравнению с вероятностными тестами.