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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
CyberGenius
 Аватар для CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
14.12.2012, 17:34     Алгоритм "Решето Эратосфена" #1
Вот наконец-то получилось реализовать это алгоритм. Укажите, пожалуйста, как можно написать красивее и рациональней?
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++ Нахождение простых чисел "решетом" Эратосфена
Решето Эратосфена C++
Решето Эратосфена C++
Решето Эратосфена C++
Решето Эратосфена C++
Используя метод "Решето Эратосфена" C++
C++ Решето Эратосфена
C++ Прокомментируйте оставшиеся строчки, не понимаю как работает "Решето Эратосфена"

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

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

Текущее время: 22:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru