Простое число
По введённому натуральному числу K
K
, не превосходящему 1000000
1
000
000
, выдать K
K
-е по счёту простое число.
Входные данные
Задано натуральное число K
K
.
Выходные данные
Выведите K
K
-е простое число.
Ограничение по времени: 2 секунды
C/C++
Задача по c++
Ё маё - три гнилых ответа! Вот миллионное простое число какое? И у меня здесь и у шизофреника в последнем коде от нейросети получается 15485863, только у меня на больших K, естественно, работает существенно быстрее! А можно сделать и ещё быстрее, если особо постараться. Второй ответ тухлый, а код из третьего ответа вообще некорректный, что ещё смешнее ответа нейросети )))
#include
#include
using namespace std;
using prime_t = unsigned;
bool is_prime(prime_t x) {
if (x == 3 || x == 5 || x == 7 || x == 11 || x == 13) {
return true;
}
if (0 == x % 3 || 0 == x % 5 || 0 == x % 7 || 0 == x % 11 || 0 == x % 13) {
return false;
}
prime_t n = static_cast(sqrt(x));
for (n = n & 1 ? n : n - 1; n * n x;
}
void get_primes(unsigned* box, const size_t n) {
box[0] = 2;
size_t i = 1;
for (auto x = 3; i < n; x += 2) {
if (is_prime(x)) {
box[i] = x;
++i;
}
}
}
int main() {
constexpr size_t n = 1'000'000;
auto primes = new unsigned[n];
get_primes(primes, n);
size_t k;
cin >> k;
cout Дмитрий Чистяков
79 688
Илья Лифанов
У Вас же код некорректный!
Айдар Есенсарин
391 судя по справочнику не является простым, а у вас присутствует в списке. Немедленно починить!
#include
#include
using namespace std;
vector primes = { 2 };
size_t tiks = 0;
bool is_prime(size_t x)
{
size_t xa = sqrt(x);
for (auto& i : primes)
{
if (i > xa) break;
if (x % i == 0) { return false;}
}
primes.push_back(x);
return true;
}
int main()
{
primes.reserve(1000000);
size_t x;
size_t tik = 2;
size_t i;
cin >> x;
if (x == 1) i = 4; else
for (i = 3; tik Арман Хасен
51 417
Дмитрий Чистяков
В онлайн компиляторе, где консоль в браузере, а алгоритм у дяди на сервере, моей программе равных нет! Проверяйте! https://www.onlinegdb.com/online_c++_compiler
За то время, пока пользователь вводит данные, пока они отправляются на сервер, и пока сервер возвращает ответ, проходит времени больше чем алгоритм, чем необходимо на заполнение моего массива. А вот вам придётся всё время складывать и всё будет зависать и тормозить :)
За то время, пока пользователь вводит данные, пока они отправляются на сервер, и пока сервер возвращает ответ, проходит времени больше чем алгоритм, чем необходимо на заполнение моего массива. А вот вам придётся всё время складывать и всё будет зависать и тормозить :)
#include
#include
int main() {
int k;
std::cin >> k;
std::vector is_prime(1000001, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i Кольян ..
25 860
Vitalia Rassoha
На одном из тестов, программа выводит ответ в неверном формате
Vitalia Rassoha
К сожалению не могу
#include
using namespace std;
bool is_prime(unsigned x) {
bool p;
if (x == 1U) p = false;
else if (x == 2U) p = true;
else if (~x & 1U) p = false;
else if (x < 8U) p = true;
else if (0U == x % 3U || 0U == x % 5U) p = false;
else {
unsigned n;
for (n = 3U; n * n x;
}
return p;
}
int main() {
auto i = 1U;
size_t k, n = 1;
cin >> k;
if (k == 1) i = 2U;
else do if (is_prime(i += 2U)) ++n; while (n < k);
cout Влад Белый
455
Vitalia Rassoha
Не проходит по времени
m = k*16; //для k <= 1000 000
(наверное коэфициент можно находить точнее, если придумать формулу. Там при k = 1000 коэфициент 8, а при 100 000 = 13.
Ну и bool[] заменить на vector<bool> чтобы памяти меньше жрало.
тогда вааще аннигиляторная пушка!