Домашние задания: Информатика

Информатика 10 класс

Срочно! Помогите, пожалуйста, с решением задачи по информатике 10 класс, с пояснением. Заранее благодарю.
Напишите программу( в Python)!!!!!!!!!!, которую ищет среди целых чисел, принадлежащих числовому отрезку (310705; 310729), простые числа, т.е. числа, имеющие ровно два различных натуральных делителя- единицу и само это число. Для каждого найденного числа Запишите его с новой строки; числа должны следовать в порядке возрастания.
Например, в диапазоне ( 10; 20) ровно четыре простых числа- 11, 13, 17 и 19, поэтому для этого диапазона ответ должен быть таким:
11
13
17
19
Акмарал Мурзагалиева
Акмарал Мурзагалиева
101
Держи, даже с лёгонькой оптимизацией перебора:
 LOW_PRIMES = [2, 3, 5]

def candidates(start, sqrstop):

    for n in LOW_PRIMES:

        if n >= start: yield n

    start = max(start, LOW_PRIMES[-1] + 1) | 1

    step = (start % 3 * 2) ^ 6

    while start * start  cand: return True

    return True



lo, hi = 310705, 310729

PRIMES = LOW_PRIMES.copy()

for cand in candidates(LOW_PRIMES[-1] + 1, hi):

    if test(cand, PRIMES[2:]): PRIMES.append(cand)

ps = (cand for cand in candidates(lo, hi * hi) if test(cand, PRIMES[2:])) 

print(*ps)
А пояснять тут особо нечего.

Перебор кандидатов в простые числа - это числа, 2, 3, 5, а затем - те, которые при делении на 6 дают остатки 1 и 5 (т.к. остальные - заведомо составные).
Простые числа до √310729 генерим и сохраняем в массив - они будут использоваться для проверки делимости. Дальше - перебор диапазона из задания с проверкой делимости, эти числа уже не сохраняются, а сразу выводятся.
СХ
Сергей Ходяков
87 571
Лучший ответ
Акмарал Мурзагалиева Огромное Вам спасибо за развернутый ответ. Очень помогли.
На PascalABC процедура поиска простых:
BETONная программа!!!
Простые:

310711
310721
310727
310729

Проверить можно при помощи программы:
function prost(n:integer):boolean;
var i:integer;
begin
if n<=1 then writeln('Числа меньше 2 не являются простыми')
else
begin
prost:=true;
for i:=2 to Round(Sqrt(n)) do
if n mod i=0 then prost:=false;
end;
end;

var x:integer;
begin
write('x=');readln(x);
if prost(x) then writeln('Простое')
else writeln('Не простое');
readln
end.
Эльвира
Эльвира
73 229

Похожие вопросы