Проверка числа на простоту

@artemchaiok2332 · Регистрация: 07.01.2018

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

Помогите решить пожалуйста, пробовал через факториал, но слишком долго получилось
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Программа должна иметь сложность O(корень из n): количество действий в программе должно быть пропорционально квадратному корню из n (иначе говоря, при увеличении входного числа в k раз, время выполнения программы должно увеличиваться примерно в корень из k раз).

@Dax · 04.01.2020, 21:45

Python
1
2
3
4
5
6
7
8
9
10
11
def IsPrime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    print(res=d * d > n)
    return res
 
 
if __name__ == '__main__':
    n = int(input())
    IsPrime(n):

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
def IsPrime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    res = d * d > n
    print(res)
    return res
 
 
if __name__ == '__main__':
    n = int(input())
    IsPrime(n)

@Andartiel · 29.04.2020, 00:48

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
 
n = int(input())
 
if n < 2:
    print("NO")
    quit()
elif n == 2:
    print("YES")
    quit()
 
i = 2
limit = int(math.sqrt(n))
 
while i <= limit:
    if n % i == 0:
        print("NO")
        quit()
    i += 1
 
print("YES")

Попробуй так

@GTim · 13.08.2020, 16:35

Python
1
2
3
4
5
6
7
def isPrime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n

@DOPIXKMNLD · 18.07.2023, 15:03

Алгоритм за O(sqrt(n))

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
 
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
 
x = int(input())
if is_prime(x):
    print("YES")
else:
    print("NO")

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@artemchaiok2332 0 / 0 / 0 Регистрация: 07.01.2018 Сообщений: 17

	Проверка числа на простоту 08.07.2018, 22:52. Показов 93958. Ответов 23 Метки python 3.x (Все метки) Помогите решить пожалуйста, пробовал через факториал, но слишком долго получилось Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Программа должна иметь сложность O(корень из n): количество действий в программе должно быть пропорционально квадратному корню из n (иначе говоря, при увеличении входного числа в k раз, время выполнения программы должно увеличиваться примерно в корень из k раз). 0