Я пытаюсь изучить Python-программирование, и я довольно новичок в этом. У меня возникали проблемы с печатью ряда простых чисел от одной до сотни. Я не могу понять, что не так с моим кодом. Вот что я написал; он печатает все нечетные числа вместо простых чисел:
for num in range(1,101): for i in range(2,num): if (num%i==0): break else: print(num) break
user1546721 23 июль 2012, в 23:07
Поделиться
Возможный дубликат Fastest способ перечислить все простые числа ниже N
Ciro Santilli 新疆改造中心996ICU六四事件 26 сен. 2015, в 14:15
is_prime = lambda n: all( n%i != 0 for i in range(2, int(n**.5)+1) )
Zaz 07 нояб. 2018, в 00:15
Поделиться:
31 ответ
Лучший ответ
Вам нужно проверить все числа от 2 до n-1 (на самом деле до sqrt (n), но хорошо, пусть это будет n). Если n делится на любое из чисел, оно не простое. Если число простое, выведите его.
for num in range(2,101): prime = True for i in range(2,num): if (num%i==0): prime = False if prime: print num
Вы можете написать то же самое намного короче и более питонично:
7.9 Простые числа. «Поколение Python»: курс для начинающих. Курс Stepik
for num in range(2,101): if all(num%i!=0 for i in range(2,num)): print num
Как я уже сказал, было бы лучше проверять делители не от 2 до n-1, а от 2 до sqrt (n):
import math for num in range(2,101): if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)): print num
Для небольших чисел, таких как 101, это не имеет значения, но для 10 ** 8 разница будет очень большой.
Вы можете немного улучшить его, увеличив диапазон, который вы проверяете, на 2 и, таким образом, проверяя только нечетные числа. Вот так:
import math print 2 for num in range(3,101,2): if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)): print num
Так как в первом цикле выбраны нечетные числа, во втором цикле нет необходимости проверять четные числа, поэтому значение ‘i’ можно начинать с 3 и пропускать до 2.
import math print 2 for num in range(3,101,2): if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)): print num
Igor Chubin 23 июль 2012, в 22:02
Поделиться
Отличная работа, но почему вы игнорируете номер 1? Один не считается простым числом. Пожалуйста, смотрите эту статью primes.utm.edu/notes/faq/one.html
Mouneer 04 июль 2015, в 18:38
Измените свой range(1,101) на range(2,101) и код будет идеальным. Давайте не будем забывать, 1 не простое число.
Akash Adhikari 01 нояб. 2017, в 13:24
Нет необходимости import math . Просто используйте **.5
Zaz 07 нояб. 2018, в 00:15
Показать ещё 1 комментарий
break завершает цикл, в котором он находится. Таким образом, вы только проверяете, делится ли он на 2, давая вам все нечетные числа.
for num in range(2,101): for i in range(2,num): if (num%i==0): break else: print(num)
что, как говорится, есть намного лучшие способы найти простые числа в python, чем это.
for num in range(2,101): if is_prime(num): print(num) def is_prime(n): for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True
Rob Wagner 23 июль 2012, в 20:51
Поделиться
Вот страница из документа Python, описывающая break / continue , с примером печати простых чисел! docs.python.org/tutorial/controlflow.html (раздел 4.4)
Простые числа (Python)
kaveman 23 июль 2012, в 20:26
Нет, вы не правы, конечно. continue здесь не поможет. Пожалуйста , напишите остроумие решения continue , если вы думаете , что вы правы
Igor Chubin 23 июль 2012, в 20:32
+1. за исключением того, что 1 не простое число. 🙂
Will Ness 24 июль 2012, в 14:29
Показать ещё 1 комментарий
Вместо пробного разделения лучший подход, изобретенный греческим математиком Эратосфеном более двух тысяч лет назад, заключается в том, чтобы просеять, многократно изгоняя кратные простые числа.
Начните с составления списка всех чисел от 2 до максимального желаемого числа n. Затем многократно принимайте наименьшее непересекающееся число и вычеркивайте все его кратные числа; числа, которые остаются непересекающимися, являются просторными.
Например, рассмотрите числа, меньшие 30. Сначала 2 обозначается как простой, затем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 и 30 являются вычеркнуто. Следующие 3 обозначены как простые, затем 6, 9, 12, 15, 18, 21, 24, 27 и 30 вычеркнуты. Следующий штрих равен 5, поэтому 10, 15, 20, 25 и 30 вычеркнуты. И так далее.
Цифры остаются неизменными: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.
def primes(n): sieve = [True] * (n+1) for p in range(2, n+1): if (sieve[p]): print p for i in range(p, n+1, p): sieve[i] = False
Оптимизированная версия сита обрабатывает 2 отдельно и решает только нечетные числа. Кроме того, поскольку все композиты, меньшие квадрата текущего штриха, пересекаются меньшими штрихами, внутренний цикл может начинаться с p ^ 2 вместо p, а внешний цикл может останавливаться у квадратного корня n. Я оставлю оптимизированную версию для работы.
Источник: overcoder.net
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Поиск простых чисел. Решето Эратосфена на Си
В этой статье поговорим о нахождении простых чисел с помощью языка программирования C. Будем использовать алгоритм, который называется «Решето Эратосфена».
В начале определение. Простое число — это такое натуральное число, которое делится само на себя и на единицу.
Дано натуральное число n, которое больше или равно двум (n>=2). Необходимо найти все простые числа, которые не больше n, то есть нужно найти все простые числа, принадлежащие отрезку [2; n]. Для поиска этих чисел будем использовать алгоритм «Решето Эратосфена». Он заключается в следующем:
- Выпишем все числа от 2 до n.
- Первое простое число 2. Присвоим это значение переменной p.
- Зачеркнем все числа в списке кратные p.
- Найдем первое незачеркнутое число, которое больше p, и присвоим переменной p это число.
- Повторяем пункты 3 и 4 до тех пор, пока это возможно. Если для данного p нету кратных чисел в списке (ничего не зачеркнули), то вычисления также закончены.
Итак, на основе этого алгоритма пишем программу:
Источник: vscode.ru
Решение задач №25 ЕГЭ информатика (Обработка целых чисел. Проверка делимости. Python)
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)
Разбирается решение задач №25 ЕГЭ информатика (Обработка целых чисел. Проверка делимости. Python). Задачи с сайта Полякова К.Ю.
Скачать:
 (Обработка целых чисел. Проверка делимости. Python) |
64.4 КБ |
Предварительный просмотр:
Подписи к слайдам:
Решение задачи 25 ЕГЭ Тема : Обработка целых чисел. Проверка делимости Что проверяется: Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации. Дрынова Светлана Викторовна
Что нужно знать : можно использовать простой перебор без оптимизации; пусть необходимо перебрать все целые числа на отрезке [ a ; b ] и подсчитать, для скольких из них выполняется некоторое условие; общая структура цикла перебора записывается так ( Python ): count = 0 for n in range(a, b+1): if условие выполнено : count += 1 print( count ) проверку условия удобно оформить в виде функции, возвращающей логическое значение ( True / False ), но можно этого и не делать
проверить делимость числа n на число d можно с помощью операции взятия остатка от деления n на x : если остаток равен 0, число n делится на x нацело проверка делимости на языке Python выглядит так: if n % d == 0: print («Делится») else : print («Не делится») для определения числа делителей натурального числа n можно использовать цикл, в котором перебираются все возможные делители d от 1 до n , при обнаружении делителя увеличивается счётчик делителей: count = 0 for d in range(1, n+1): if n % d == 0: count += 1 print ( count ) # вывести количество делителей
перебор делителей можно оптимизировать, учитывая, что наименьший из пары делителей, таких что a b = n , не превышает квадратного корня из n ; нужно только аккуратно обработать случай, когда число n представляет собой квадрат другого целого числа (можно не оптимизировать для нахождения количества делителей); если требуется определить не только количество делителей, но и сами делители, нужно сохранять их в массиве в языке Python удобно использовать динамический массив: сначала он пуст, а при обнаружении очередного делителя этот делитель добавляется в массив: divs = [] for d in range (1, n +1): # перебор всех возможных делителей if n % d == 0: # если нашли делитель d divs . append ( d ) # то добавили его в массив
простое число n делится только на 1 и само на себя, причём единица не считается простым числом; таким образом, любое простое число имеет только два делителя для определения простоты числа можно считать общее количество его делителей; если их ровно два, то число простое, если не два – не простое: nDel = 0 # количество делителей числа for d in range (1, n +1): # все возможные делители if n % d == 0: nDel += 1 # нашли ещё делитель if nDel == 2: print( » Число простое » ) else: print ( «Число составное» )
работу программы можно ускорить: если уже найдено больше двух делителей, то число не простое и можно досрочно закончит работу цикла с помощью оператора break : nDel = 0 # количество делителей числа for d in range (1, n +1): # все возможные делители if n % d == 0: nDel += 1 # нашли ещё делитель if nDel > 2: # уже не простое число break # досрочный выход из цикла if nDel == 2: print ( «Число простое» ) else : print ( «Число составное» ) другой вариант – считать количество делителей числа на отрезке [2; n– 1]; как только хотя бы один такой делитель будет найден, можно завершить цикл, потому что число явно не простое:
Задача 1. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Решение 1. Для того чтобы вообще избавиться от работы с дробными числами, удобно заменить условие d d: divs.append ( n//d ) if len ( divs ) > divCount : break d += 1 if len ( divs ) == divCount : print ( * divs )
Решение 2. Так как здесь нам нужно выводить все делители, кроме единицы и самого числа, в цикле перебора делителей начинаем с 2 и включаем N, если очередной делитель d –это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей ( d , x // d ): from math import sqrt divCount = 2 # нужное количество делителей for n in range(174457, 174505+1): divs = [] q = int (sqrt(n)) for d in range(2,q+1): if n % d == 0: if d == n//d: divs = divs + [d] else: divs = divs + [d, n//d] if len ( divs ) > divCount : break if len ( divs ) == divCount : print( * divs )
Решение 3. Можно построить массив делителей на языке Python можно и с помощью генератора списка: for n in range ( 174457; 174505 +1): divs = [d for d in range(1, n+1) if n % d == 0] if len ( divs ) = = 2 : print( * divs ) Аналогично можно построить массив делителей, удовлетворяющих заданному условию, например, всех чётных делителей: for n in range( 174457 , 174457 +1): divs = [d for d in range(1, n+1) if n % d == 0 and d % 2 == 0 ] if len ( divs ) == 4 : print( * divs )
Решение 4. ещё один вариант программы (с функцией, которая возвращает массив делителей): def allDivisors (n): divs = [] for d in range(1,n+1): if n % d == 0: divs.append (d) return divs for n in range( 174457; 174505 +1): divs = allDivisors (n) if len ( divs ) == 2 : print( * divs )
Решение 5. (программа без массива): учитывая, что в этой задаче нас интересуют только два делителя, можно вместо массива использовать две дополнительных переменные for i in range (174457, 174505+1): k = 0; for j in range (2, i ): if i % j == 0: k = k + 1; if k == 1: d1 = j if k == 2: d2 = j if k == 2: print( d1, d2 )
Задача 2.Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [3532000; 3532160], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку. from math import sqrt count = 0 for n in range(3532000, 3532160+1): prime = True for d in range(2, round(sqrt(n))): if n % d == 0: prime = False break if prime: count += 1 print( count, n ) Решение 1.
Решение 2. компактное решение, использующее встроенную функцию all – она возвращает логическое значение T rue , если все элементы переданного ей списка равны T ru e ; возвращает F alse , если хотя бы один из них равен F alse ( если у ‘n’ нет делителей от 2 до корня из n т.е. все ‘d’ дают остаток отличный от нуля): count=0 for n in range(3532000,3532160+1): if all( n%d !=0 for d in range(2,round(n**0.5)+1) ): count+=1 print ( count,n )
Решение 3. вариант с функцией isPrime , которая возвращает логическое значение True (истина) для простых чисел и False (ложь) для составных: from math import sqrt def isPrime (n): for d in range(2, round(sqrt(n)+1) ): if n % d == 0: return False return True count = 0 for n in range(3532000, 3532160+1): if isPrime (n): count += 1 print( count, n )
По теме: методические разработки, презентации и конспекты
Урок математики с ЭОР в 5 классе по теме «Решение задач на нахождение части от целого и целого по его части»
План-конспект урока по математике. 5 класс.
Презентация к уроку по теме «Решение задач на нахождение части от целого и целого по его части». Математика. 5 класс.
Презентация к уроку по теме «Решение задач на нахождение части от целого и целого по его части». Математика. 5 класс.
проект урока по теме «Решение задач на отыскание части от целого и целого по его части»
решение задач на нахождение части от целого и целого по его части
презентация для закрепления навыков по темам решение задач на нахождение части от целого и целого по его части.
«Решение задач на кратное и разностное сравнение чисел» Урок для обучающихся 5 класса коррекционной школы
Урок для обучающихся 5 класса коррекционной школы.
Использование модуля itertools в Python при решении задач на уроках информатики по теме «Комбинаторика».
Очень часто на уроках информатики встречаются задачи перебора различных вариантов последовательностей, состоящих из букв или цифр. Данный класс задач встречается и в Компьютерном ЕГЭ. С 2022 года форм.
Подготовка к ЕГЭ по информатике. Разбор задания 25 Обработка целых чисел. Проверка делимости.
Материал представлен в виде презентации. Основная цель — научить создавать программы для обработки целочисленной информации, нахождения делителей и обработки простых чисел. Рассмотрены разные типы зад.
Источник: nsportal.ru