2015-11-19 3 views
0

Мне был предоставлен код ниже, он передает число, чтобы проверить, является ли оно простым. Я не понимаю, что делает floor(sqrt(toCheck)) +1 или что делает переменная prb. Я думаю, что он запускает цикл while, тогда как bool noFactorFound является истинным, а prb меньше searchLimit. Все встало бы на свои места, если бы я знал, как инициализирован searchLimit.Поиск кода первичного номера C++

#include<cmath> //for floor() & sqrt() 

#include "prime.h" 

bool isPrime(unsigned toCheck) 
{ 
    if (toCheck== 2) 
     return true; 
    if ((toCheck % 2) == 0) 
     return false; 
    unsigned prb = 3; 
    unsigned searchLimit = floor(sqrt(toCheck)) + 1; 
    bool noFactorFound = true; 
    while (noFactorFound && (prb<searchLimit)) 
    { 
     if ((toCheck % prb) == 0) 
      noFactorFound = false; 
     else 
      prb += 2; 
    } 
    return (noFactorFound); 
} 
+2

http://www.cppreference.com/w/cpp/numeric/math/sqrt, числовой/математика/этаж) –

ответ

1

Причины инициализации предела поиска sqrt(N)+1 является то, что если число больше, чем sqrt(N)+1 делит N, то число меньше sqrt(N)+1 бы также разделить его, так как возникают факторы, в парах (кроме sqrt(N), который включен в диапазоне поиска).

Функция sqrt находит квадратный корень из числа. Floor округляет плавающее число до наибольшего целого числа ниже, чем поплавок.

Выполняется +1, чтобы избежать пропусков на номера из-за округления функцией floor. Альтернативой будет использование функции ceil, без необходимости использования +1.

1

Когда вы ищете факторы числа, вам не нужно искать числа, которые больше квадратного корня этого числа. Поэтому, в конце концов, когда мы зацикливаемся, мы хотим только увеличивать столько индексов, сколько квадратный корень.

floor(sqrt(toCheck)) + 1; 

Это квадратный корень toCheck. Однако sqrt возвращает float, и наши индексы цикла являются целыми числами unsigned s, поэтому мы берем дробную часть с floor, затем добавляем ее к ней, чтобы избежать пропущенного фактора, если это произошло путем округления.

Многое из этого можно понять, внимательно прочитав документацию, поэтому я бы посоветовал сделать это, столкнувшись с подобными проблемами.