Прост број - Решење

Линеарна претрага свих потенцијалних делилаца

Природан број је прост ако је већи од 1 и ако није дељив ни са једним бројем осим са један и са самим собом. По дефиницији број 1 није прост. Дакле, број већи од 1 је прост ако нема ни једног правог делиоца. Потребно је дакле извршити претрагу скупа потенцијалних делилаца и проверити да ли неки од њих стварно дели број \(n\). Имплементација се заснива на алгоритму линеарне претраге. Скуп потенцијалних делилаца је скуп свих природних бројева од \(2\) до \(n-1\) и наивна имплементација их све проверава.

#include <iostream>

using namespace std;

// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
  if (n == 1) return false;
  for (int i = 2; i < n; i++)
    if (n % i == 0)
      return false;
  return true;
}

int main() {
  int n;
  cin >> n;
  cout << (prost(n) ? "DA" : "NE") << endl;
  return 0;
}

Одсецање у претрази

Делиоци броја се увек јављају у пару. На пример, делиоци броја 100 организовани по паровима су (1, 100), (2, 50), (4, 25) (5, 20) и (10, 10). Ако је \(i\) делилац броја \(n\), делилац је и број \(\frac{n}{i}\). При том, ако је \(i \geq \sqrt{n}\), тада је \(\frac{n}{i} \leq \sqrt{n}\). Дакле, важи следећа теорема.

Теорема. Природан број \(n \geq 2\) има праве делиоце који су већи или једнаки вредности \(\sqrt{n}\) ако и само ако има делиоце који су мањи или једнаки вредности \(\sqrt{n}\).

Ова теорема нам даје могућност да претрагу потенцијалних делилаца редукујемо само на интервал \([2, \sqrt{n}]\), јер ако број нема делилаца мањих или једнаких вредности \(\sqrt{n}\), онда не може да има делилаца већих или једнаких тој вредности, тј. нема правих делилаца и прост је. Ово је пример алгоритма у ком се ефикасност значајно поправља тако што је елиминисан (одсечен) значајан део простора претраге за који можемо да докажемо да га није неопходно проверавати.

Сама имплементација је једноставна и заснива се на алгоритму линеарне претраге. У посебној функцији на почетку проверавамо специјалан случај броја 1 (ако је \(n\) једнако 1, враћамо вредност false). Након тога, у петљи проверавамо потенцијалне делиоце од 2 до \(\sqrt{n}\). Један начин да одредимо горњу границу је да употребимо библиотечку функцију sqrt. Међутим, рад са реалним бројевима је могуће у потпуности избећи тако што се уместо услова \(i \leq \sqrt{n}\) употреби услов \(i\cdot i \leq n\). За сваку вредност \(i\) проверава се да ли је делилац броја \(i\) (израчунавањем остатка при дељењу). Чим се утврди да је \(i\) делилац броја \(n\) функција може да врати false (тиме се уједно прекида извршавање петље). На крају петље, функција може да врати true, јер није пронађен ниједан делиоц мањи или једнак од \(\sqrt{n}\), па на основу теореме које смо доказали не може постојати ни један делилац изнад те вредности и број је прост.

#include <iostream>

using namespace std;

// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
  if (n == 1) return false;
  for (int i = 2; i*i <= n; i++)
    if (n % i == 0)
      return false;
  return true;
}

int main() {
  int n;
  cin >> n;
  cout << (prost(n) ? "DA" : "NE") << endl;
  return 0;
}

Могуће је правити и другачије имплементације истог алгоритма.

#include <iostream>

using namespace std;

// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
  int i = 2;
  while (i*i <= n && n % i != 0)
    i++;
  return n > 1 && i*i > n;
}

int main() {
  int n;
  cin >> n;
  cout << (prost(n) ? "DA" : "NE") << endl;
  return 0;
}

Провера само непарних бројева

Још једна могућа оптимизација је да се на почетку провери да ли је број паран а да се након тога проверавају само непарни делиоци, међутим, та оптимизација не доноси превише (обилазак до корена смањује број потенцијалих кандидата са милијарде на тек тридесетак хиљада, а провера само непарних делилаца тај број смањује на петнаестак хиљада, што је сразмерно знатно мања уштеда).

#include <iostream>

using namespace std;

// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
  if (n == 1) return false;     // broj 1 nije prost
  if (n == 2) return true;      // broj 2 jeste prost
  if (n % 2 == 0) return false; // ostali parni brojevi nisu prosti
  // proveravamo neparne delioce od 3 do korena iz n
  for (int i = 3; i*i <= n; i += 2)
    if (n % i == 0)
      return false;
  // nismo nasli delioca - broj jeste prost
  return true;
}

int main() {
  int n;
  cin >> n;
  cout << (prost(n) ? "DA" : "NE") << endl;
  return 0;
}

Провера само бројева облика 6k-1 и 6k+1

Програм се још мало може убрзати ако се примети да су сви прости бројеви већи од 2 и 3 облика \(6k-1\) или \(6k+1\), за \(k \geq 1\) (наравно, обратно не важи). Заиста, бројеви облика \(6k\), \(6k+2\) и \(6k+4\) су сигурно парни тј. дељиви са \(2\), бројеви облика \(6k+3\) су дељиви са \(3\), тако да су једини преостали \(6k+1\) и \(6k+5\), при чему су ови други сигурно облика \(6k'-1\) (за \(k' = k+1\)). Дакле, уместо да проверавамо дељивост са свим непарним бројевима мањим од корена, можемо проверавати дељивост са свим бројевима облика \(6k-1\) или \(6k+1\), чиме избегавамо проверу са једним на свака три непарна броја и програм убрзамо сходно томе.

#include <iostream>
using namespace std;

// funkcija koja proverava da li je dati broj prost
bool prost(int n) {
  if (n == 1 ||
      (n % 2 == 0 && n != 2) ||
      (n % 3 == 0 && n != 3))
    return false;
  for (int k = 1; (6*k - 1) * (6*k - 1) <= n; k++)
    if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0)
      return false;
  return true;
}

int main() {
  int n;
  cin >> n;
  cout << (prost(n) ? "DA" : "NE") << endl;
}

Ако је потребно за више бројева одједном проверити да ли су прости, уместо проверавања сваког појединачног, боље је употребити Ератостеново сито. Тај алгоритам је описан у задатаку Ератостеново сито.