Я пишу небольшую библиотеку с некоторыми методами, связанными с числом чисел. Поскольку я сделал основы (также методы работы), и теперь я ищу некоторую оптимизацию. Конечно, интернет - отличное место для этого. Я, однако, наткнулся на проблему округления, и мне было интересно, как это решить.
В цикле я использую для проверки числа для его примитивности, более эффективно искать до 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, примерно с теми же результатами.
