| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [C++]поиск простых чисел методом решета |
| Автор: liss87 28.11.2007, 23:17 |
| Здравствуйте. Помогите,пожалуйста,написать программу. Требуется разработать программу для поиска простых чисел в заданном промежутке,верхняя и нижняя границы которого заданы.(например,передаются через командную строку) Поиск должен осуществляться по методу решета Эрастофена. Программа должна быть написана на языке С++ с использованием линейного списка. Алгоритм поиска с помощью решета таков: Выпишем последовательность всех натуральных чисел от 2 до n. Алгоритм нацелен на то, чтоб вычеркнуть все составные числа. Тогда оставшиеся числа будут простыми. Число 1,как известно, не является ни простым, ни составным, поэтому в реализации алгоритма не участвует. Будем просматривать последовательность слева направо. Первое попавшееся число-это 2,оно является простым. Далее будем вычеркивать из последовательности каждое второе число, потому что данные числа уже заведомо будут являться составными(потому что уже делятся на 2 ). Следующее невычеркнутое число-3,оно также является простым. Вычеркиваем из оставшейся последовательности каждое третье число. 4 будет вычеркнуто как четное(действительно,4-составное число). Следующее невычеркнутое число-5,вычеркиваем каждое пятое число. Затем вычеркиваем каждое седьмое число, каждое одиннадцатое и так далее до тех пор, пока не будут вычеркнуты все составные числа. Как я понимаю,для этого решета создается определенное количество объектов класса List,а при вычеркинвании из решета составных чисел динамически освобождается память,и список с каждой итерацией становится все меньше и меньше. заранее спасибо. |
| Автор: GIK 29.11.2007, 11:43 | ||
Чет я смысла этих действий не могу понять. каждое второе, каждое третье??? для чего, и в чем логика? Другое дело просто написать алгоритм который отбрасывает все составные числа. Не понимаю я чет  |