Минимальный простой делитель
Дано целое число, не меньшее 2. Выведите его наименьший простой делитель
Вводится целое положительное число N⩽2⋅10^9.
Выведите ответ на задачу.
#include <iostream>
using namespace std;
int main()
{
long long n;
long long m = 2;
long long k = 124;
cin >> n;
if (n % 2 != 0){
while ( m * m <= n && k != 0){
m = m + 1;
k = n % m;
}
}
if (m * m >= n){
cout << n;
}else{
cout << m;
}
}
что не так с программой? сколько бы чисел вводить не пробовал, всегда верный результат. а пишет, что программа выдает неверный ответ, не проходит она проверку.
#include <iostream>
using namespace std;
bool is_prime(const unsigned n, unsigned m = 2) {
if (m > (n >> 1)) return true;
return n % m ? is_prime(n, ++m) : false;
}
bool is_even(const unsigned n) {
return !(n % 2U);
}
bool is_divider(const unsigned n, const unsigned d) {
return 0U == n % d;
}
unsigned min_prime_divider(const unsigned n) {
if (is_even(n)) return 2U;
const auto m = n >> 1;
auto i = 3U;
while (i <= m) {
if (is_divider(n, i) && is_prime(i)) return i;
i += 2U;
}
return n;
}
unsigned number(const char* msg = ">>> ", const double lim = 2e9) {
auto value = 0U;
while (value < 2U || value > lim) {
cout << msg;
cin >> value;
}
return value;
}
int main() {
while(true) {
const auto n = number();
const auto m = min_prime_divider(n);
cout << "<<< " << m << '\n';
}
}
Попробуйте квадрат простого числа. Например, 49.
Я бы лучше так сделала:
#include <cmath>
#include <iostream>
using namespace std;
unsigned long *a, b[32], c[32];
void fal(unsigned long x)
{ a[x >> 5] &= c[x & 31]; }
unsigned bit(unsigned long x)
{ return a[x >> 5] & b[x & 31]; }
int main()
{ unsigned long i = 1, j, k, l, m, n = 46340, N;
b[0] = i; c[0] = ~i; for (j = 1; j < 32; j++) { i <<= 1;
b[j] = i; c[j] = ~i; } m = ceil((n + 1.) / 32);
a = new unsigned long [m]; for (i = 0; i <= m; i++)
a[i] = 4294967295; fal(0); fal(1); i = ceil(sqrt(n));
for (j = 2; j <= i; j++) if (bit(j)) { k = n / j; for (l = 2;
l <= k; l++) fal(l * j); } while (true) { cout << "N: ";
cin >> N; if (N == 2) { cout << N << endl;
goto end; } if (N % 2 == 0) cout << 2 << endl; else
{ for (j = 3; j <= i; j += 2) if (bit(j)) if (N % j == 0)
{ cout << j << endl; goto end; } cout << N << endl; }
end:; } }
Это правильно, надёжно и очень быстро.
Число 4 введите. Какой ответ выдает программа и какой у числа 4 наименьший простой делитель?
