Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
1 / 1 / 1
Регистрация: 21.10.2013
Сообщений: 115

Прокомментируйте оставшиеся строчки, не понимаю как работает "Решето Эратосфена"

15.06.2015, 13:03. Показов 748. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream> //подключение стандартной библиотеки ввода-вывода
using namespace std; //пространство имён. Чтобы писать "cout << endl;" вместо "std::cout << endl;"
 
static const int N = 1000; //глобальная переменная. В данном случае (слово const) это константа, то есть изменить её значение невозможно. Сразу записываем её значение (1000)
 
int main()//главная функция. Здесь стартует программа.
{
int i, a[N]; //переменная i целого типа и целочисленный массив размером 1000
 
for (i = 2; i < N; i++) a[i] = 1; 
 
for (i = 2; i < N; i++){
  if (a[i])
    for (int j = i; j*i < N; j++) a[i*j] = 0;
}
 
for (i = 2; i < N; i++)
if (a[i]) cout << " " << i;
cout << endl;
return 0; //выход из программы
}//конец главной функции
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
15.06.2015, 13:03
Ответы с готовыми решениями:

Как работает блочное решето Эратосфена?
Доброго времени суток. У меня к вам такой вопрос, как работает блочное решето Эратосфена, я нашел реализацию, но как оно работает не могу...

Решето Эратосфена (сегмент): медленно работает - как можно ускорить?
Подсчёт числа простых чисел в диапазоне от &quot;from&quot; до &quot;to&quot; typedef UINT64 Number; __device__ Number eratosthenesSingleBlock(const...

Решето Эратосфена (работает некорректно)
вроде компилируется однако не работает корректно #include&lt;stdio.h&gt; int main() { int n,j,c; int i = 2;

4
67 / 67 / 72
Регистрация: 10.04.2015
Сообщений: 281
15.06.2015, 18:17
Цитата Сообщение от Аннaa Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream> //подключение стандартной библиотеки ввода-вывода
using namespace std; //пространство имён. Чтобы писать "cout << endl;" вместо "std::cout << endl;"
static const int N = 1000; //глобальная переменная. В данном случае (слово const) это константа, то есть изменить её значение невозможно. Сразу записываем её значение (1000)
int main()//главная функция. Здесь стартует программа.
{
int i, a[N]; //переменная i целого типа и целочисленный массив размером 1000
for (i = 2; i < N; i++) a[i] = 1; //Заполняем в цикле элементы массива a (a[i]), i=2,3...998,999  числом 1.
for (i = 2; i < N; i++){//Цикл от 2 до N-1(см.выше)
if (a[i])//Если элемент "i" массива "a" не является нулём, то:
for (int j = i; j*i < N; j++) a[i*j] = 0; //цикл по 'j'. Начальное значение j = i. Условие выполнения: пока j*i будут меньше N. После каждого шага цикла увеличиваем переменную j на один.
}
for (i = 2; i < N; i++) // от 2 до N-1
if (a[i]) cout << " " << i; //если элемент 'i' массива "а" отличен от нуля - выводим пробел и индекс этого элемента.
cout << endl;//перенос строки с очисткой буфера.
return 0; //выход из программы
}//конец главной функции
как-то так.
1
Просто Лис
Эксперт Python
 Аватар для Рыжий Лис
5973 / 3735 / 1099
Регистрация: 17.05.2012
Сообщений: 10,791
Записей в блоге: 9
15.06.2015, 20:52
Всё равно понятней не стало. Попробую-ка словами.
Создаётся массив из 1000 элементов. (берётся первая тысяча натуральных чисел 0, 1, 2, 3... 998, 999)
Каждое из чисел помечается флагом.

Берётся первое число (это двойка).
(начало цикла)
Если текущее число не было вычеркнуто, то из массива вычёркиваются числа кратные ему (4, 6, 8...)
Берётся следующее число. (тройка, четвёрка...)
(повторить цикл) пока число текущее число не равно 1000.

Все не вычеркнутые числа выводим на экран.
1
88 / 84 / 31
Регистрация: 18.11.2013
Сообщений: 390
15.06.2015, 22:29
обьясню алгоритм, числом 0 в массиве помечаются НЕ простые числа, изначально все числа простые, заполнены единицой

потом мы убераем все числа, которые можно разложить на два множителя, сначала убираем все, которые можно разложить на 2*j, потом 3*j и так далее, т.к. они уже не являются простыми т.к. делятся на эти 2 числа
j мы подбираем до тех пор, пока i*j меньше максимального размера, т.к. дальше они просто будут увеличиваться

ну и потом выводим все простые числа, то есть все, элемент в массиве которых равен единице
1
1 / 1 / 1
Регистрация: 21.10.2013
Сообщений: 115
15.06.2015, 22:47  [ТС]
Спасибо, теперь понятнее стало
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
15.06.2015, 22:47
Помогаю со студенческими работами здесь

Решето Эратосфена. Как ускорить?
Этот код не проходит задачу. доля секунды. как ускорить. или каким методом проидет #include &lt;bits/stdc++.h&gt; using namespace...

Как реализовать решето Эратосфена для длинных чисел?
Длинные числа у меня хранятся как строки

Как разложить число на простые множители, используя решето Эратосфена?
Я только код для решета Эратосфена знаю(

Как оптимизировать расход памяти, чтобы решето Эратосфена работало на бОльших числах?
int main() { unsigned long long int n= 1&lt;&lt;20; char str; memset (str,'1',n); for (unsigned long long int i =...

Решето Эратосфена
Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru