Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
#1

Алгоритм "Решето Эратосфена" - C++

14.12.2012, 17:34. Просмотров 1172. Ответов 2
Метки нет (Все метки)

Вот наконец-то получилось реализовать это алгоритм. Укажите, пожалуйста, как можно написать красивее и рациональней?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
vector<int> all;//Здесь храняться все числа от 0 до n
    int n= 0; //верхний предел
    int p = 2; //первое простое число
    cin>>n;
 
    for(int i = 0; i<=n; ++i){//Заполнение вектора all
        all.push_back(i);
    }
 
    while(p*p<n){
 
        for(int i = p; i<=n - p; i +=p ){//Заполнение нулями чисел кратных p
            all[i + p] = 0;//Чтобы не заполнять число равное all[i]
        }
    
        int k = p;//НУжно сохранить значение р, т.к дальше в цикле оно изменяется, а нужно использовать имено это значение
 
        for(int i = n; i>=k+1; --i){//Проходим весь вектор и если all[i] не равно 0, то присваеваем р его значение.
            //К+1 используем для того, чтобы не записать в р уже использованое значение
            //т.е чтобы алгоритм опять не просчитывался при р=2; 
 
            if(all[i]!=0){
                p =all[i];
            }
        }
    }
 
    for(int i = 2; i<=n; ++i){//Опять проходим весь вектор и выводим все all[i] не равные 0
        if(all[i]!=0){
            cout<<all[i]<<endl;
        }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.12.2012, 17:34     Алгоритм "Решето Эратосфена"
Посмотрите здесь:

Алгоритм "Решето Эратосфена" - C++
тыкните в чем проблема пожалуйста... void Eratosfen(int N) { int size_array = N - 2; int *array = new int; for (int i = 0;...

Написать программу с использованием алгоритма "Решето Эратосфена" - C++
Написание программу с использованием алгоритма &quot;Решето Эратосфена &quot;.&quot;, Которая подсчитывает все простые числа в диапазоне от 2 до 2000000...

Прокомментируйте оставшиеся строчки, не понимаю как работает "Решето Эратосфена" - C++
#include &lt;iostream&gt; //подключение стандартной библиотеки ввода-вывода using namespace std; //пространство имён. Чтобы писать &quot;cout &lt;&lt;...

Используя метод "Решето Эратосфена" - C++
Помогите пожалуйста Используя метод &quot;Решето Эратосфена&quot;, по заданному натуральному 7V&gt;1 найти все простые числа, меньшие...

Нахождение простых чисел "решетом" Эратосфена - C++
Здравствуйте! Вроде так почитал - на вид несложный метод, но как-то туплю. Помогите пожалуйста.

Решето Эратосфена - C++
В общем задание посчитать количество простых чисел до заданного числа N. Написал такой алгоритм, работает только до 11 :cry: Уже час не...

Решето Эратосфена - C++
Здравствуйте. Реализовал алгоритм &quot;Решето Эратосфена&quot; в виде класса. Взгляните, пожалуйста, и скажите, где я не прав. Спасибо. ...

Решето Эратосфена - C++
Подскажите реализацию (код) метода шифрования - решета Эратосфена, пожалуйста.

Решето Эратосфена - C++
Написать функция для выполнения алгоритма решить Эратосфена! зарания спасибо!!!

Решето Эратосфена - C++
Определить простые числа методом просеивания с помощью &lt;&lt;решета Эратосфена&gt;&gt; с _битовой упаковкой_ данных при сохранении. #include...

Решето Эратосфена - C++
Кому надо - программа &quot;Решето Эратосфена&quot; на C++. Записывает в файл 1 000 000 первых простых чисел за 1/10 секунды (без вывода)!!! ...

Решето Эратосфена - C++
Дано число N (2&lt;=N &lt;=10000), найдите и выведите простые числа между 2 и данным N. Простое число - число, которое может быть разделено...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
14.12.2012, 17:37     Алгоритм "Решето Эратосфена" #2
Использовать iterator
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
14.12.2012, 17:38  [ТС]     Алгоритм "Решето Эратосфена" #3
Цитата Сообщение от sovaz1997 Посмотреть сообщение
Использовать iterator
А что такое iterator, я пока не знаю
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru