Задача на С++. Минимальный простой делитель

Question

Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. Вводится целое положительное число N≤2∗109. Выведите ответ на задачу. Вот мой код:

#include <iostream>
using namespace std;
int main()
{
    long long i = 3, n;
    cin >> n;
    if (n % 2 == 0) cout << 2;
    else {
        while (n % i != 0) {
            i += 2;
        }
        cout << i;
    }
}

Его проблема в том, что мне пишет: Программа выполнялась слишком долго и была прервана. Я хочу узнать, как это исправить и получается ускорить процесс.

Answer 1

Попробуйте так:

#include <iostream>
using namespace std;
int main()
{
    long long i = 3, n;
    cin >> n;
    if (n % 2 == 0) cout << 2;
    else {
        while(n%i && i*i <= n) {
            i += 2;
        }
        cout << ((n%i) ? n : i);
    }
}

Answer 2

вот мой код, прошел по всем ограничениям по времени (так как сравнивал не с самим числом, а с корнем из него)

#include <iostream>
using namespace std;

int main() {
    int x, i=2, f=1;
    cin >> x;
    while (i * i <= x && f==1) {
        if (x % i != 0) {
            i = i + 1;
        }
        else {
            f = 0;
        }
    }
    if (x % i == 0) {
        cout << i;
    } else {
        cout << x;
    }
    return 0;
}

БЛОГ НА HUSL

Задача на С++. Минимальный простой делитель

Ответы (2 шт):