第 8 集 · B1 · 7 分钟
C 语言 · 第8集 · 素数筛
从 Hello World、循环、递归讲到汉诺塔和动态规划，句子短，适合跟读。 开头：记录了一些数字，我限制在
中俄字幕
записаны некоторые числа, я ограничился
记录了一些数字，我限制在
диапазоном 40.
40以内。
требуется найти все простые числа в этом диапазоне.
需要找出该范围内的所有质数。
В чем состоит идея?
其核心思想是什么？
Берем первое число, двойку, и зачеркиваем все числа, кратные ему.
取第一个数2，然后划掉所有它的倍数。
Затем, то есть пробегаем по всему, ну у нас это будет массив, да, и отмечаем.
接着，即遍历整个数组（是的，这里用的是数组）并做标记。
Я на самом деле буду отмечать единичкой, начальное состояние будет ноликами массив у
实际上，我将用数字1来标记；数组初始状态全为0，
меня будет заполнен, и вот соответствующие индексы я буду выставлять в единичку.
我的数组会被填满，对应索引位置将设为1。
Затем берем следующее число и зачеркиваем все числа для него.
接着取下一个数，并划掉它的所有倍数。
Я не могу и не буду перепроверять, зачеркнуто ли оно уже, я просто буду выставлять
我不会也不必重复检查某个数是否已被划掉，我只是直接设置标记。
единичку повторно, это не будет ничего отменять.
重新标记数字1，这不会取消任何操作。
Но тем не менее, да, все кратные трем зачеркиваем.
但无论如何，是的，所有3的倍数都要划掉。
Таким образом у меня окажутся зачеркнуты все кратные трем.
这样，所有3的倍数就都被划掉了。
Сейчас маленькое усовершенствование будет.
接下来要做一个小优化。
все кратные трём зачёркиваются, естественно, что тут находится достаточно большое
所有3的倍数都会被划掉，显然这里会有很多个。
количество. Ой, прошу прощения, через, да, вот так, тридцать.
数量。哎呀，抱歉，是‘通过’，对，就这样，30。
35, я зря 35 я сейчас не должен был вычеркнуть.
35，我误划了35，我现在本不该划掉它。
36. 36 и 39, вот еще зачеркивается из- за тройки.
36。36和39，因3而被划掉。
Затем ничего страшного не будет, если я для четвёрки тоже пробегусь.
然后，我再检查一遍4，也不会有什么问题。
Можно было бы и это скипнуть, да, не делать, потому что, естественно, что все числа,
其实可以跳过这一步，是的，不必做，因为显然所有数字都……
кратные четырём, они уже кратны двум.
能被4整除的数，必然也能被2整除。
Потому что оно уже составное, да.
因为它本来就是合数，对吧。
Но ничего страшного, если бы мы и пробежались.
但也没关系，即使我们真的逐一检查一遍。
Потом для пятерки, соответственно, что 10, 15, 20, 25.
接着轮到5，相应地划掉10、15、20、25。
Но вы можете заметить, что первые два зачёркивания, они как бы лишние.
但你们可能注意到，前两次划掉的操作其实是多余的。
первое реально новое число, с которого надо начинать, это 25.
真正需要从5开始划掉的第一个新数是25。
Вот первое зачёркнутое число реально из за пятерки это 25, да, заметили?
实际上，第一个因5而被划掉的数就是25，注意到了吗？
Сейчас давайте посмотрим, какое новое число зачёркнётся из за семёрки.
现在我们来看看，因7而被划掉的第一个新数是什么。
первое число которое зачеркнется из за семерки.
第一个因7而被划掉的数。
а уже нету тут такого числа, которое бы требовалось реально зачеркнуть новое.
而这里已经没有真正需要新划掉的数了。
На самом деле первое, которое нужно будет зачеркнуть из за семерки, это семью семь
实际上，第一个需要因7而划掉的数是7乘以7
сорок девять. а все числа, которые здесь остались на доске, это все уже простые
即49。黑板上剩余的所有数字都是质数
числа. Это на самом деле не материал информатики, это материал школьной математики,
这些内容其实不属于计算机科学，而是中学数学的内容
но простите за повторение, поскольку мне требуется этот алгоритм сейчас реализовать.
抱歉重复一下，因为接下来我需要实现这个算法
и его невозможно реализовать без использования массива.
而且不使用数组就无法实现该算法
потому что мне требуется повторное, многократное обращение к одним и тем же ячейкам.
因为我需要反复、多次访问相同的内存单元
Там стоит единичка, не стоит единичка, составное это число или простое.
某个位置上标有数字1，还是没有标1，该数是合数还是质数
Давайте напишем вместе эту программу.
我们一起来编写这个程序吧
я сделал заготовку, в которой я просто распечатываю массив.
我已经准备了一个模板，它只是简单地打印出整个数组
размером 20. Ну вот, сейчас выводит мне 20
数组大小为20。现在它输出了20个数字
ноликов. Видите, да?
零。看到了吗？
Ничего особенного.
没什么特别的。
Есть одна маленькая особенность.
有一个小细节。
Вот этот 3D никакого отношения к 3D графике не имеет.
这里的“3D”与3D图形毫无关系。
Вот это 3- это количество.
这个‘3’指的是位数。
символов, в которые должно поместиться число.
即数字必须能放入指定数量的字符中。
Естественно, что если это число окажется слишком большим, то
显然，如果这个数字过大，
оно просто не будет помещаться.
它就根本无法显示出来。
Зачем я это сделал?
我为什么要这么做？
В решете у меня будут храниться либо нолики, либо единички, то есть у меня флажковая
我的筛子中只存储0或1，也就是一个标志数组。
будет флажковая информация, простой или составной.
将显示标志信息，表示该数是质数还是合数。
Простой ноль, составной один.
质数用0表示，合数用1表示。
но и сделал я это для того, чтобы рядом с вот этими состояниями напечатать.
我还特意这样安排，以便在这些状态旁边打印出来。
напечатать еще и номера,
再打印出对应的编号，
то есть. и сделать это так, чтобы они помещались в ту же самую ширину, в три
也就是说，让它们都占据相同的宽度——三个字符。
символа. В результате у меня будет такое вот красивое выравнивание для чисел,
结果，我的数字就能整齐美观地对齐，
видите, да? То есть я вижу в какой именно ячейке каково состояние моего решета.
您看到了吧？这样我就能清楚知道筛子中每个格子对应的状态。
Между прочим, я вот сюда вписал дополнительно перевод каретки, который у меня. . .
顺便提一下，我额外添加了一个换行符，它……
ну и здесь тоже я в конце его сделаю, чтобы у меня красивенько это дело выглядело.
最后这里我也加上一个换行符，让整个输出看起来更美观。
Давайте еще раз оценим оформление того, как мы увидим наше решение, получившееся
我们再来整体评估一下最终解法的输出格式。
решето Эратосфена.
埃拉托斯特尼筛法。
Теперь осталось.
现在只剩下……
при помощи циклов повозиться в этом решете и,
用循环来操作这个筛子，并
ну, собственно, организовать вот этот вот алгоритм.
嗯，实际上就是实现这个算法。
Начинаем с двойки.
从数字2开始。
То есть наш алгоритм.
也就是说，我们的算法
он начинается с двоечки,
从数字2开始，
int i равно 2.
int i 等于 2。
Далее что мы делаем?
接下来我们做什么？
i меньше чем. . .
i 小于……
А, кстати, вот до куда реально нам надо двигаться.
啊，对了，这就是我们实际需要达到的目标。
Вы, наверное, заметили, что я на доске не стал продолжать этот алгоритм для семёрки,
您可能已经注意到，我在黑板上没有继续对数字7执行这个算法，
для 11. ну для 11 я же мог тоже там 22 зачеркнуть но ведь я же понимаю что я все
对11也是一样。其实我本也可以划掉22，但我清楚地知道，
равно не могу найти при помощи решета эратосфена все вообще простые числа это их
我根本无法用埃拉托斯特尼筛法找出所有素数，因为素数有无穷多个。
бесконечное количество поэтому я ограничиваюсь каким то числом граница диапазона
因此，我只能限定一个范围上限。
есть. И в рамках этой границы диапазона до неё мне имеет смысл зачёркивать только те
这个范围上限是存在的。在该上限范围内，我只需划掉那些尚未被划掉的数。
числа, которые ещё не зачёркнуты.
而尚未被划掉的数。
А первая зачёркиваемая для 11 будет 121.
而11的第一个要划掉的数是121。
Понимаете? Мне даже уже семёрка реально не требуется, семёрки в рамках 40
明白吗？实际上，对于40以内的范围，我甚至根本不需要用到7。
зачёркивать. Реально я могу как отслеживать верхнюю границу, говорить, что i меньше,
实际上，我可以通过跟踪上限来判断，即判断i是否小于该上限。
чем корень из n.
比n的平方根小。
Но чтобы не пользоваться функцией корня, я использую
但为了避免使用开方函数，我采用
просто i умноженное на i.
简单的i乘以i。
То есть i квадрат меньше, ну на самом деле либо равно n, то есть на всякий случай
也就是说，i的平方要小于（实际上等于或小于）n，以防万一，
надо этот. равенство пройти.
需要包含这个等号。
И увеличиваем на единичку, окей.
然后将i加1，好的。
Значит, что я делаю?
那么，我在做什么？
вот здесь вот у меня вот здесь вот будет вложенный цикл for.
这里将有一个嵌套的for循环。
то есть мне нужно для каждого i пробежать по индексам в этом массиве и отметить
也就是说，对每个i，我需要遍历该数组中的索引，并进行标记，
единичками, начиная с какого.
从某个位置开始。
Опять же, можно было бы с 2 умноженное на i,
同样，也可以从 2 乘以 i 开始，
но правильнее с i квадрата начинать бежать.
但更合适的做法是从 i 的平方开始。
Запускаем for int k равно с i квадрата.
我们启动一个 for 循环，令整型变量 k 等于 i 的平方。
Соответственно, k у меня меньше n.
相应地，我的 k 小于 n。
Ой, простите, пожалуйста, а почему у меня n не входит?
哎呀，抱歉，请问为什么我的 n 不包含在内？
У меня i, прошу прощения, недопустимое вот это вот.
我的 i，抱歉，是无效的，就是这个。
来源：Тимофей Хирьянов · CC BY 3.0