Ближайшее простое

@Artem302 · Регистрация: 19.09.2022

Студворк — интернет-сервис помощи студентам

Здравствуйте, помогите пожалуйста исправить(доработать код) или написать новый, как кому будет удобно с++ - python.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from itertools import count
 
def prime(n):
    for i in range(2, (n // 2) + 1):
        if n % i == 0:
            return False
    else:
        return True
 
def prime_closest_to(n):
    for i in count(n):
        if prime(i):
            x = i
            dx = x - n
            break
    for j in count(n - 1, 1):
        if prime(j):
            y = j
            dy = n - y
            break
    ret = x if dx < dy else y
    return ret
 
n = int(input())
print(prime_closest_to(n))

1 WA 0 0,000 2 740,0k
2 OK 4,80 0,000 2 752,0k
3 OK 4,80 0,000 2 704,0k
4 OK 4,80 0,000 2 724,0k
5 OK 4,80 0,001 2 756,0k
6 OK 4,80 0,000 2 704,0k
7 OK 4,80 0,000 2 792,0k
8 OK 4,80 0,000 2 788,0k
9 OK 4,80 0,000 2 736,0k
10 OK 4,80 0,000 2 744,0k
11 OK 4,80 0,001 2 752,0k
12 OK 4,80 0,001 2 736,0k
13 WA 0 0,000 2 788,0k
14 WA 0 0,000 2 776,0k
15 OK 4,80 0,000 2 744,0k
16 TL 0 0,203 2 788,0k
17 TL 0 0,204 2 808,0k
18 TL 0 0,203 2 796,0k
19 OK 4,80 0,000 2 744,0k
20 TL 0 0,205 2 728,0k

Вердикт Опис вердикту
OK
Accepted. Рішення успішно відпрацювало на вказаному тесті. Якщо такий вердикт отримано на всіх тестах, це означає, що ви повністю вирішили завдання.

CE
Compilation Error. Помилка компіляції. Компілятор не створив файл, що виконується. Вам надається повне виведення компілятора. Можливі причини: синтаксична помилка в програмі, при відправці була вказана неправильна мова програмування.

PE
Presentation Error. Неправильний формат виводу. На вказаному тесті програма виводить дані, які не відповідають умові завдання. Можливі причини: програма виводить у вихідні дані сторонній текст; програма виводить недостатню кількість вихідних даних; використовується файлове введення/виведення і вихідний файл вказаний у програмі неправильно; вихідні дані взагалі створюються.

WA
Wrong Answer. На цьому тесті ваше рішення видає неправильну відповідь. Можливі причини: реалізований неправильний алгоритм, відбулося переповнення в цілісній змінній, речові значення виводяться з недостатньою точністю.

TL
Time Limit Exceeded. На цьому тесті перевищено час виконання програми, тобто. ваша програма працює довше, ніж допустимо для цього завдання. Можливі причини: алгоритм через помилку входить до безкінечного циклу; написаний алгоритм розв'язання задачі має неправильну асимптотику, тобто є неоптимальним та його треба спробувати покращити.

ML
Memory Limit Exceeded. На зазначеному тесті перевищено огранічні пам'яті, тобто. Ваша програма вимагає більше оперативної пам'яті, ніж допустимо для цього завдання. Можливі причини: алгоритм використовує великі структури даних; в алгоритмі відбувається дуже багато рекурсивних викликів.

RE
Runtime Error. На вказаному тесті програма неправильно завершила роботу, іншими словами, сталася помилка під час виконання програми. Можливі причини: розподіл на нуль, вилучення кореня квадратного з негативного числа, звернення до неіснуючих елементів масиву чи рядка тощо.

FF
Forbiden Function. Заборонена функція. На вказаному тесті програма викликала одну з функцій, яка може порушити роботу системи тестування.

@Red white socks · 20.09.2022, 01:05

Код в тегах выкладывайте

@Catstail · 20.09.2022, 08:36

Замени:

Python
1
2
3
4
5
6
7
8
def prime(n):
    q=int(n**0.5)+1
    k=2
    while k<=q:
          if n%k==0:
             return False
          k+=1
    return True

@Artem302 · 20.09.2022, 08:54 **[ТС]**

Здравствуйте! Заменил, ушла ошибка TL, но все также некоторые тесты не проходит.

1 WA 0 0,000 2 708,0k
2 OK 4,80 0,000 2 732,0k
3 OK 4,80 0,000 2 780,0k
4 OK 4,80 0,000 2 744,0k
5 OK 4,80 0,000 2 772,0k
6 OK 4,80 0,001 2 740,0k
7 OK 4,80 0,001 2 728,0k
8 OK 4,80 0,001 2 784,0k
9 OK 4,80 0,002 2 792,0k
10 OK 4,80 0,002 2 724,0k
11 OK 4,80 0,003 2 772,0k
12 OK 4,80 0,002 2 748,0k
13 WA 0 0,001 2 788,0k
14 WA 0 0,000 2 760,0k
15 OK 4,80 0,000 2 744,0k
16 WA 0 0,007 2 788,0k
17 OK 4,80 0,006 2 808,0k
18 OK 4,80 0,003 2 724,0k
19 WA 0 0,000 2 748,0k
20 OK 4,80 0,006 2 800,0k

@Red white socks · 20.09.2022, 08:59

Artem302, , в соседней теме решето Эратосфена написано

Добавлено через 2 минуты
И условие задачи приведите все-таки.

@eaa · 20.09.2022, 09:04

Red white socks, не решето. 10⁹ ограничения.

@Catstail · 20.09.2022, 09:07

Artem302, WA - неверный ответ. Не исключено, что дело в единице:

Python
1
2
3
4
5
6
7
8
9
10
def prime(n):
    if n<=1:
       return False
    q=int(n**0.5)+1
    k=2
    while k<=q:
          if n%k==0:
             return False
          k+=1
    return True

@Red white socks · 20.09.2022, 09:19

eaa, а, точно.

@Artem302 · 20.09.2022, 09:28 **[ТС]**

Вот задача:

Задача - Ближайшее простое
Ограничение по времени: 0.2
Ограничение по памяти: 64
Напишите программу, которая находит ближайшее к заданному натуральному N простое число.

Формат входных данных
Во входных данных записано одно натуральное число N(1 <= N <= 2*10^9)

Формат выходных данных
Выведите ближайшее к заданному числу N простое число. Если таких чисел окажется два, то надо вывести меньшее

Тест Ответ
10 11

12 11

9 7

5 5

Добавлено через 4 минуты

Есть еще такой код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def is_prime(num):
    d = 2
    if num > 1:
        while (num % d) != 0:
            d = d + 1
    return (d == num)
arg = int(input())
plus = arg
minus = arg
res = 0
res1 = 0
res2 = 0
if not is_prime(arg):
    while not is_prime(plus):
        plus = plus + 1
    while not is_prime(minus):
        if minus == 1:
            minus = -1
            break
        minus = minus - 1
    if (arg - minus) > (plus - arg):
        res = plus
        print(res)
    elif (arg - minus) < (plus - arg):
        res = minus
        print(res)
    else:
        res1 = minus
        res2 = plus
        print(res1)

@eaa · 20.09.2022, 09:32

Artem302, код оформи нормально

Добавлено через 2 минуты
Red white socks, хотя. до корня, то мы можем в принципе запомнить простые числа. даже до 10⁵. дальше будет TLE

@Red white socks · 20.09.2022, 09:33

Artem302, В 16 строке поставьте шаг -1.
Вообще count здесь сомнительная идея

@Artem302 · 20.09.2022, 09:34 **[ТС]**

К сожалению ничего не изменилось.

@Red white socks · 20.09.2022, 09:37

eaa, по простым перебирать или по всем до корня - особо разницы здесь нет. Просто думал, что готовое решение уже есть.

Добавлено через 1 минуту

Сообщение от Artem302

К сожалению ничего не изменилось.

В смысле не изменилось?))
Что-то да должно было

@Artem302 · 20.09.2022, 09:39 **[ТС]**

Я оформил его нормально, дело в системе, которая скомкала его.

Вот в тхт файле!

@Artem302 · 20.09.2022, 09:41 **[ТС]**

Простите, может я немного не правильно сказал, прошу за это прощения. Системы оценки дотс как не пропускала некоторые тесты, так и не пропускает.

1 WA 0 0,000 2 748,0k
2 OK 4,80 0,000 2 680,0k
3 OK 4,80 0,000 2 768,0k
4 OK 4,80 0,000 2 700,0k
5 OK 4,80 0,000 2 772,0k
6 OK 4,80 0,000 2 720,0k
7 OK 4,80 0,000 2 772,0k
8 OK 4,80 0,000 2 716,0k
9 OK 4,80 0,000 2 744,0k
10 OK 4,80 0,000 2 756,0k
11 OK 4,80 0,000 2 804,0k
12 OK 4,80 0,000 2 720,0k
13 WA 0 0,000 2 744,0k
14 WA 0 0,000 2 728,0k
15 OK 4,80 0,000 2 756,0k
16 WA 0 0,012 2 784,0k
17 OK 4,80 0,011 2 784,0k
18 OK 4,80 0,003 2 752,0k
19 WA 0 0,000 2 736,0k
20 OK 4,80 0,007 2 792,0k

@Red white socks · 20.09.2022, 09:43

Artem302, шаг на -1 исправили?

@Artem302 · 20.09.2022, 09:48 **[ТС]**

Да, сейчас исправил, получилось, но 1 тест)
1 OK 4,80 0,000 2 748,0k
2 OK 4,80 0,000 2 760,0k
3 OK 4,80 0,000 2 772,0k
4 OK 4,80 0,000 2 748,0k
5 OK 4,80 0,000 2 792,0k
6 OK 4,80 0,000 2 744,0k
7 OK 4,80 0,000 2 760,0k
8 OK 4,80 0,000 2 772,0k
9 OK 4,80 0,000 2 724,0k
10 OK 4,80 0,000 2 752,0k
11 OK 4,80 0,000 2 712,0k
12 OK 4,80 0,000 2 740,0k
13 OK 4,80 0,000 2 808,0k
14 OK 4,80 0,000 2 744,0k
15 OK 4,80 0,000 2 800,0k
16 OK 4,80 0,007 2 796,0k
17 OK 4,80 0,008 2 800,0k
18 OK 4,80 0,004 2 732,0k
19 TL 0 0,203 2 768,0k
20 OK 4,80 0,004 2 792,0k

@eaa · 20.09.2022, 09:57

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isprime(n):
    i = 2
    while i * i <= n and n % i != 0:
        i += 1
    return i * i > n
 
 
n = int(input())
n1 = n2 = n
while not isprime(n1):
    n1 += 1
while not isprime(n2):
    n2 -= 1
n2 += n2 == 1
if 2 * n > n1 + n2:
    print(n1)
else:
    print(n2)

@Artem302 · 20.09.2022, 09:59 **[ТС]**

Спасибо большое, все работает, всем большущее спасибо

@Red white socks · 20.09.2022, 10:03

Python
1
2
3
4
5
6
7
8
def prime_closest_to(n):
    if prime(n):
        return n
    for d in count(1)
        if prime(n-d):
            return n-d
        if prime(n+d):
            return n+d

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.09.2022, 01:05
	Код в тегах выкладывайте 0

@Artem302 0 / 0 / 0 Регистрация: 19.09.2022 Сообщений: 14
	20.09.2022, 08:54 [ТС]
	Здравствуйте! Заменил, ушла ошибка TL, но все также некоторые тесты не проходит. 1 WA 0 0,000 2 708,0k 2 OK 4,80 0,000 2 732,0k 3 OK 4,80 0,000 2 780,0k 4 OK 4,80 0,000 2 744,0k 5 OK 4,80 0,000 2 772,0k 6 OK 4,80 0,001 2 740,0k 7 OK 4,80 0,001 2 728,0k 8 OK 4,80 0,001 2 784,0k 9 OK 4,80 0,002 2 792,0k 10 OK 4,80 0,002 2 724,0k 11 OK 4,80 0,003 2 772,0k 12 OK 4,80 0,002 2 748,0k 13 WA 0 0,001 2 788,0k 14 WA 0 0,000 2 760,0k 15 OK 4,80 0,000 2 744,0k 16 WA 0 0,007 2 788,0k 17 OK 4,80 0,006 2 808,0k 18 OK 4,80 0,003 2 724,0k 19 WA 0 0,000 2 748,0k 20 OK 4,80 0,006 2 800,0k 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.09.2022, 08:59
	Artem302, , в соседней теме решето Эратосфена написано Добавлено через 2 минуты И условие задачи приведите все-таки. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	20.09.2022, 09:04
	Red white socks, не решето. 10⁹ ограничения. 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.09.2022, 09:19
	eaa, а, точно. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	20.09.2022, 09:32
	Artem302, код оформи нормально Добавлено через 2 минуты Red white socks, хотя. до корня, то мы можем в принципе запомнить простые числа. даже до 10⁵. дальше будет TLE 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.09.2022, 09:33
	Artem302, В 16 строке поставьте шаг -1. Вообще count здесь сомнительная идея 0

@Artem302 0 / 0 / 0 Регистрация: 19.09.2022 Сообщений: 14
	20.09.2022, 09:34 [ТС]
	К сожалению ничего не изменилось. 0

@Artem302 0 / 0 / 0 Регистрация: 19.09.2022 Сообщений: 14
	20.09.2022, 09:41 [ТС]
	Простите, может я немного не правильно сказал, прошу за это прощения. Системы оценки дотс как не пропускала некоторые тесты, так и не пропускает. 1 WA 0 0,000 2 748,0k 2 OK 4,80 0,000 2 680,0k 3 OK 4,80 0,000 2 768,0k 4 OK 4,80 0,000 2 700,0k 5 OK 4,80 0,000 2 772,0k 6 OK 4,80 0,000 2 720,0k 7 OK 4,80 0,000 2 772,0k 8 OK 4,80 0,000 2 716,0k 9 OK 4,80 0,000 2 744,0k 10 OK 4,80 0,000 2 756,0k 11 OK 4,80 0,000 2 804,0k 12 OK 4,80 0,000 2 720,0k 13 WA 0 0,000 2 744,0k 14 WA 0 0,000 2 728,0k 15 OK 4,80 0,000 2 756,0k 16 WA 0 0,012 2 784,0k 17 OK 4,80 0,011 2 784,0k 18 OK 4,80 0,003 2 752,0k 19 WA 0 0,000 2 736,0k 20 OK 4,80 0,007 2 792,0k 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	20.09.2022, 09:43
	Artem302, шаг на -1 исправили? 0

@Artem302 0 / 0 / 0 Регистрация: 19.09.2022 Сообщений: 14
	20.09.2022, 09:48 [ТС]
	Да, сейчас исправил, получилось, но 1 тест) 1 OK 4,80 0,000 2 748,0k 2 OK 4,80 0,000 2 760,0k 3 OK 4,80 0,000 2 772,0k 4 OK 4,80 0,000 2 748,0k 5 OK 4,80 0,000 2 792,0k 6 OK 4,80 0,000 2 744,0k 7 OK 4,80 0,000 2 760,0k 8 OK 4,80 0,000 2 772,0k 9 OK 4,80 0,000 2 724,0k 10 OK 4,80 0,000 2 752,0k 11 OK 4,80 0,000 2 712,0k 12 OK 4,80 0,000 2 740,0k 13 OK 4,80 0,000 2 808,0k 14 OK 4,80 0,000 2 744,0k 15 OK 4,80 0,000 2 800,0k 16 OK 4,80 0,007 2 796,0k 17 OK 4,80 0,008 2 800,0k 18 OK 4,80 0,004 2 732,0k 19 TL 0 0,203 2 768,0k 20 OK 4,80 0,004 2 792,0k 0

@Artem302 0 / 0 / 0 Регистрация: 19.09.2022 Сообщений: 14
	20.09.2022, 09:59 [ТС]
	Спасибо большое, все работает, всем большущее спасибо 0

Ближайшее простое

Решение