Question

ДАЮ ВСЕ БАЛЛЫ!!! МИНИМАЛЬНЫЙ ПРОСТОЙ ДЕЛИТЕЛЬ НА С++!!!!

Дано целое число, не меньшее 2. Выведите его наименьший простой делитель.

Входные данные

Вводится целое положительное число N≤2∗109.

Выходные данные

Выведите ответ на задачу.

Примеры

Ввод
15
Вывод
3
Скорее, плиз!!!!!!!!!!

Answer 1

#include <iostream>

#include <cmath>

using namespace std;

bool isPrime(int n) {

   if (n <= 1)

       return false;

   if (n == 2)

       return true;

   if (n % 2 == 0)

       return false;

   int sqrtN = sqrt(n);

   for (int i = 3; i <= sqrtN; i += 2) {

       if (n % i == 0)

           return false;

   }

   return true;

}

int smallestPrimeDivisor(int n) {

   if (n <= 1)

       return 0;

   if (isPrime(n))

       return n;

   int sqrtN = sqrt(n);

   for (int i = 2; i <= sqrtN; i++) {

       if (n % i == 0 && isPrime(i))

           return i;

   }

   return n;

}

int main() {

   int n;

   cin >> n;

   int smallestDivisor = smallestPrimeDivisor(n);

   cout << smallestDivisor << endl;

   return 0;

}