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

Question

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

Денис Гайсин Ученик (137), закрыт 1 час назад

помогите с задачей на c++

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

Поиск делителя при этом целесообразно осуществлять не до самого числа (которое может оказаться очень большим), а до квадратного корня из этого числа. Если делитель не нашелся до корня, то число точно простое.

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

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

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

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

я вот так делал и ошибка на 9 тесте

#include <iostream>
#include <cmath>

using namespace std;

int main() {
int n, m = 2, s = 0;
cin >> n;
while (pow(m, 2) != n) {
if (n % m == 0) {
s = s + 1;
break;
}
else {
m = m + 1;
}
}
if (n == 4) {
cout << 2;
}
else if (s == 0) {
cout << n;
}
else {
cout << m;
}
return 0;
}

Answer 1

 #include <cmath> 
#include <iostream> 
#include <vector>

using namespace std;

class Primes { 
public: 
    using prime_t = unsigned; 
    explicit Primes(const prime_t limit) : limit(limit) { 
        fill(); 
    } 
    prime_t least_prime_divisor(const prime_t value) const { 
        for (auto prime : primes) { 
            const auto x = value / prime; 
            const auto y = x * prime; 
            if (y == value) return prime; 
        } 
        return value; 
    } 
private: 
    prime_t limit; 
    vector<prime_t> primes; 
    void fill() { 
        const auto mid = static_cast<prime_t>(sqrt(limit)); 
        vector<bool> is_prime(mid + 1, true); 
        is_prime[0] = is_prime[1] = false; 
        for (prime_t i = 2; i <= mid; ++i) { 
            if (is_prime[i]) { 
                for (prime_t j = i * i; j <= mid; j += i) { 
                    is_prime[j] = false; 
                } 
            } 
        } 
        for (prime_t i = 2; i <= mid; ++i) { 
            if (is_prime[i]) { 
                primes.push_back(i); 
            } 
        } 
    } 
};

int main() { 
    constexpr Primes::prime_t limit{ 2'000'000'000 }; 
    Primes primes(limit);  
    unsigned value; 
    cin >> value; 
    cout << primes.least_prime_divisor(value) << '\n'; 
}

Answer 2

твоя ошибка в условии цикла. условие while(pow(m, 2) != n) неверно, потому что оно не охватывает случаи, когда число – полный квадрат, например, 49. если n = 49, то цикл остановится, когда m станет равным 7 (потому что 7² = 49), и деление на 7 так и не будет проверено. получается, что переменная s остаётся нулевой и выводится само число 49, хотя нужно вывести 7.

решение – нужно перебирать делители пока m² не превысит n, то есть использовать условие while(m*m <= n) или аналогичный цикл for.

 #include <iostream> 
using namespace std; 
 
int main() { 
    int n; 
    cin >> n; 
     
    for (int m = 2; m * m <= n; m++) { 
        if (n % m == 0) { 
            cout << m; 
            return 0; 
        } 
    } 
    cout << n; // если делитель не найден, n – простое число 
    return 0; 
}