Как узнать простые числа?

@vnyzaica · Регистрация: 26.02.2017

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

Есть строка с числами. Как узнать какие из этих чисел простые?
К примеру строка 1 10 31 991 1111
И вывод 1 31 991

@Joey · 18.11.2017, 17:18

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

И вывод 1 31 991

1 не является простым числом.

Есть много методов. Выберем один.
Сначала выясняем, является ли число четным:

Python
1
2
if n % 2 > 0:
    #значит не простое

Также проверяем, если число меньше 3, значит оно либо простое, либо 1 или 0.
Затем просто перебираем делители от 3 до n / 2 (число1 никак не поделится на число2, большее, чем половина числа1)

@vnyzaica · 18.11.2017, 18:57 **[ТС]**

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

1 не является простым числом.

Есть много методов. Выберем один.
Сначала выясняем, является ли число четным:

Python
1
2
if n % 2 > 0:
    #значит не простое

Также проверяем, если число меньше 3, значит оно либо простое, либо 1 или 0.
Затем просто перебираем делители от 3 до n / 2 (число1 никак не поделится на число2, большее, чем половина числа1)

Этот способ хороший и я о нем в начале и подумал,но проблема состоит в том что нужно проверять число от 100000... А находить все делители до 100000 сложно,муторно и наверняка не рационально

@Joey · 18.11.2017, 22:48

vnyzaica, есть такое. Тогда почитайте https://ru.wikihow.com/%D0%BF%... 1%8B%D0%BC разные методы

vic5710 · 18.11.2017, 23:17

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

нужно проверять число от 100000

из топика "как ускорить..." вычисли массив простых чисел, а потом проверяй свои на вхождение

@Joey · 18.11.2017, 23:27

vnyzaica, возьмите на вооружение совет от vic5710, только немного модификации:
1. Находите наибольшее из Ваших чисел;
2. Вычисляете массив простых чисел до этого числа;
3. Проверяете свои на вхождение

@vnyzaica · 18.11.2017, 23:59 **[ТС]**

Окей попробую.

vic5710 · 19.11.2017, 02:08

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

попробую.

для проверки все вычислять не надо

Python
1
2
3
4
5
6
7
8
9
10
import math
def primes(n):
    a = [True]*n
    for i in range(2, math.ceil(math.sqrt(n))):
        if a[i]:
            for j in range(i*2 , n, i): a[j] = False
    return a
 
def isprime(num,arr):
    return arr[num]

Python
1
2
3
4
5
>>> arr = primes(1000000)
>>> isprime(997,arr)
True
>>> isprime(1001,arr)
False

Добавлено через 12 минут
тока надо добавить

Python
1
2
a[0] = False
a[1] = False

Новые блоги и статьи Все статьи Все блоги /
Вывод данных через динамический список в справочнике Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .

@vnyzaica 0 / 0 / 0 Регистрация: 26.02.2017 Сообщений: 59

	Как узнать простые числа? 18.11.2017, 14:54. Показов 7905. Ответов 7 Метки питон, простые, простые числа, числа (Все метки) Есть строка с числами. Как узнать какие из этих чисел простые? К примеру строка 1 10 31 991 1111 И вывод 1 31 991 0

@Joey Джоуи 1083 / 645 / 240 Регистрация: 05.05.2015 Сообщений: 3,559 Записей в блоге: 2
	18.11.2017, 22:48
	vnyzaica, есть такое. Тогда почитайте https://ru.wikihow.com/%D0%BF%... 1%8B%D0%BC разные методы 1

@Joey Джоуи 1083 / 645 / 240 Регистрация: 05.05.2015 Сообщений: 3,559 Записей в блоге: 2
	18.11.2017, 23:27
	vnyzaica, возьмите на вооружение совет от vic5710, только немного модификации: 1. Находите наибольшее из Ваших чисел; 2. Вычисляете массив простых чисел до этого числа; 3. Проверяете свои на вхождение 1

@vnyzaica 0 / 0 / 0 Регистрация: 26.02.2017 Сообщений: 59
	18.11.2017, 23:59 [ТС]
	Окей попробую. 0