@want_my_dream

Привет, совсем недавно начал изучать С++, читаю книгу, да и до этого как-то были аленькие опыты, так вот, есть код:
Он выводи все простые числа в диапазоне от 2 до 1000, так написано в книге, он действительно это делает. Но я что-то не могу уловить сути, а именно эту часть. Как-то не до конца понимаю, как это работает. Поможете объяснить?

0

@_Ivana

Напишите название книги, в которой приведен этот образец гениальности - делить на 4, 6 и т.д. если не поделилось на 2.

0

@Otello

Он выводит не все числа от 2 до 1000. А лишь ту часть, которая подходит под условия.

0

@want_my_dream

Герберт Шилдт C++ базовый курс 3-е издание

Добавлено через 11 минут
Я сейчас просто распишу, как я рассуждаю:
i=2 оно <1000, поэтому входит в цикл, j=2 и j<=(i/j), то есть 2<=2/2 --> 2<=1, то есть не подходит, значит первое if не выполняется, переходим ко второму if, где 2>2/2 --> 2>1, что верно, поэтому первым простым числом является 2. i=2+1=3, j=2+1=3. Все начинается опять с первого for. i=3<1000, входит, j=3<=3/3, что опять неверно, идем во второй if, 3>3/3, да, подходит. i=3+1=4, j=3+1=4. У нас уже два числа: 2 и 3. Сначала, i=4<1000, j=4<=4/4, не подходит, идем во второй if, 4>4/4, да. подходит, то есть 2, 3 и 4, но 4 не является простым, это я так думаю, как все это происходит, но нет, при выводе там получаются только простые числа, 2, 3, 5 и т.д. Возможно я чего-то не понимаю, но чего? Насколько я понимаю, первый if исполнялся бы только если условие второго for было истиной, но, когда я считаю получается всегда ложь и первое if никогда не выполняется. Вроде до этого, как-то разбирался в if и for, до этого момента...

0

KOPOJI

Минимум упрощений, вариант "в лоб" - цикл от 2 до i. Следуя же вашему замыслу, проверок будет куда больше - на 3, на 5, на 7 и т.д. В общем, на все простые числа от 2 до i включительно. А затем проверять, а делится ли i на то самое простое число. Ну или наоборот, сначала проверить, делится ли i на простое число, а затем проверить, делится ли шаг на простое число. Перефразирую: а оно надо в книге для новичков?

0

@Otello

Ошибочка. Во втором пункте j равно 2, потому что цикл 2 запущен заново, значит сначала j=2; 2<=3/2...

0

@want_my_dream

Хм... А зачем тогда j++?

0

@_Ivana

KOPOJI, мне просто стало любопытно, в какой такой книге пишется подобная чушь. И что эти книги еще и читают и по ним пытаются учиться.

0

KOPOJI

want_my_dream, простое число - число, которое делится только на само себя и на единицу. Поэтому вложенный цикл проверяет все числа от 2 до текущего числа, чтобы узнать, делится i на еще какое-то число из диапазона [2, i)

Добавлено через 1 минуту
_Ivana, это же не книга по алгоритмизации.. Имхо, вполне нормально дать такой вариант (а если дальше еще есть и сноска на то, что код неоптимизированный или оптимизации в качестве задания - то и вообще отлично).

0

@Otello

Прочитай как работает for и ещё раз подумай.

0

KOPOJI

0

@_Ivana

справедливости ради - до корня. На это авторов все-таки хватило.

0

KOPOJI

0

@Otello

Я не тебе

0

@want_my_dream

Таакс.. Я прогнал числа от 2 до 10 через свою думалку, ответы получались правильные: 2, 3, 5, 7... Пока я не дошел до проверки 11, у меня получается, что 11 не подходит... 2<=11/2. да, 11%2, с остатком, но !, следовательно первый if пропускаем, далее, насколько я понял, тут-то значению j и прибавляется 1, т.к. условие выполнилось....... Все, я понял... Вроде бы понял!) После, когда j=3, второе if тоже не выполнилось, следовательно возвращаемся обратно во вложенный цикл, то есть, условие выполняется, j опять получает +1, в итоге 4, и тогда уже значение 4>11/4 верное, 11 является простым числом! Омг, скажите мне, что я правильно думаю.

0

@Renji

Плохо работает.
1) Число является простым, если делится только на единицу и само себя.
2) Если число А имеет делители отличные от единицы и А, то хотя-бы один из них будет не больше корня квадратного из А.
3) Следовательно, для проверки на простоту, нужно перебрать делители от двух до корня квадратного из А. Циклом for (j = 2; j <= sqrt(i); j++)
4) Далее автор вашего кода думает "э, sqrt работает медленно, сейчас я оптимизирую!" и втыкает j <= (i / j) с ровно тем же смыслом.

Теперь глядите. sqrt(i) считается долго. Но его можно посчитать один раз, а потом записать в условие цикла j <= sqrt_i. С другой стороны (i / j) считается заметно быстрее, но его придется считать на каждой итерации цикла. А деление, между-прочим, тоже далеко не самая быстрая операция. Итого, погнавшись за крутым решением, автор вашего учебника получил мало того что плохой, так еще и трудночитаемый код.

0

@_Ivana

1. Корень можно посчитать целочисленно Ньютоном, будет быстро и без матха и без перевода в плавучку и обратно.
2. Можно и умножать для проверки диапазона вместо деления, хотя если в списке команд процессора есть мул и див, то все равно не так долго будет считать. А нет их разве что на АВР тини или ПИКах каких-нибудь нижней линейки.
3. А можно воспользоваться доказанной гипотезой Бертрана, и складывать уже найденные простые числа в массив, проверяя следующие на деление только на элементы этого массива - там их всегда будет достаточно, что гарантируют Бертран с Чебышёвым.

0

@want_my_dream

Спасибо всем

0