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

Решето Эратосфена - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
vortexx1
 Аватар для vortexx1
6 / 6 / 2
Регистрация: 06.03.2011
Сообщений: 269
30.11.2011, 02:04     Решето Эратосфена #1
Здравствуйте. Реализовал алгоритм "Решето Эратосфена" в виде класса.
Взгляните, пожалуйста, и скажите, где я не прав. Спасибо.

C++
1
2
3
4
5
6
7
8
class EratosphenesSieve
{
public:
    EratosphenesSieve( int );
    ~EratosphenesSieve();
private:
    bool *sieve;
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cmath>
#include "EratosphenesSieve.h"
 
EratosphenesSieve::EratosphenesSieve( int n )
{
    n = abs( n );
    *sieve = new bool[ n + 1 ];
    
    for( int i = 0; i <= n; i++ )
        sieve[ i ] = true;
        
    for( int i = 2; i <= n; i++ )
        for( int k = i + 1; k <= n; k++ )
             if( k % i == 0 )
                 sieve[ k ] = false;                           
}
 
EratosphenesSieve::~EratosphenesSieve()
{
    delete [] sieve;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.11.2011, 02:04     Решето Эратосфена
Посмотрите здесь:

C++ Решето Эратосфена
Решето Эратосфена C++
Решето Эратосфена C++
Решето Эратосфена C++
C++ Решето Эратосфена
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
30.11.2011, 02:22     Решето Эратосфена #2
Цитата Сообщение от vortexx1 Посмотреть сообщение
Здравствуйте. Реализовал алгоритм "Решето Эратосфена" в виде класса.
Взгляните, пожалуйста, и скажите, где я не прав. Спасибо.

C++
1
2
3
4
5
6
7
8
class EratosphenesSieve
{
public:
    EratosphenesSieve( int );
    ~EratosphenesSieve();
private:
    bool *sieve;
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cmath>
#include "EratosphenesSieve.h"
 
EratosphenesSieve::EratosphenesSieve( int n )
{
    n = abs( n );
    *sieve = new bool[ n + 1 ];
    
    for( int i = 0; i <= n; i++ )
        sieve[ i ] = true;
        
    for( int i = 2; i <= n; i++ )
        for( int k = i + 1; k <= n; k++ )
             if( k % i == 0 )
                 sieve[ k ] = false;                           
}
 
EratosphenesSieve::~EratosphenesSieve()
{
    delete [] sieve;
}
Сначала по определению самого класса. Если вы считаете, что вам должны указать неотрицательное число, то задавайте тип параметра как unsigned int. В вашем классе желательно хранить заданный размер последовательности целых чисел, чтобы знать, какая последовательность была рассмотрена.
Очевидно, что объект вашего класс не имеет смысла присваивать другому объекту вашего класса, так как не понятна семантика такого присваивания, а потому конструктор копирования и копирующий оператор присваивания лучше сделать закрытыми. Также желательно иметь два метода. первый возвращает размер вашей последовательности, а второй выводит на основе вашего логического массива те значения чисел, для которых вы получили значение true.

Поэтому я бы класс объявил следующим образом

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class EratosphenesSieve
{
public:
    EratosphenesSieve( unsigned int );
    ~EratosphenesSieve();
    unsigned int size() const;
    std::ostream & out( std::ostream & ) const;
private:
    bool *sieve;
    unsigned int n;
private:
    EratosphenesSieve( const EratosphenesSieve &  );
    EratosphenesSieve & operator =( const EratosphenesSieve & );
};
 
std::ostream & operator <<( std::ostream &os, const EratosphenesSieve &rhs )
{
   return ( rhs.out( os ) );
}
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.11.2011, 12:40     Решето Эратосфена #3
Цитата Сообщение от Сыроежка Посмотреть сообщение
то задавайте тип параметра как unsigned int.
Лучше все же size_t написать.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.11.2011, 12:49     Решето Эратосфена #4
Сложность вашего алгоритма http://www.cyberforum.ru/cgi-bin/latex.cgi?O(n^2), а можно сделать http://www.cyberforum.ru/cgi-bin/latex.cgi?O(n\cdot sqrt{n})
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.11.2011, 13:25     Решето Эратосфена #5
Thinker, ты про это?
C
1
for( int i = 2; i <= n; i++ )
C
1
i * i <= n;
vortexx1
 Аватар для vortexx1
6 / 6 / 2
Регистрация: 06.03.2011
Сообщений: 269
30.11.2011, 14:48  [ТС]     Решето Эратосфена #6
Начинать с квадрата числа, да + числа УЖЕ вычеркнутые можно не делить, а просто пропускать.
Спасибо за комментарии.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.11.2011, 15:57     Решето Эратосфена #7
Цитата Сообщение от fasked Посмотреть сообщение
Thinker, ты про это?
C
1
for( int i = 2; i <= n; i++ )
C
1
i * i <= n;
Смотря как связать эти инструкции
Сыроежка
Заблокирован
30.11.2011, 16:10     Решето Эратосфена #8
vortexx1, Вам просто надо начинать с проверки элемента 2 * исходный элемент и далее расмаатривать элементы i * исходный элемент < размер последовательности.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2011, 16:15     Решето Эратосфена
Еще ссылки по теме:

C++ Решето Эратосфена
Решето Эратосфена C++
C++ Решето Эратосфена

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.11.2011, 16:15     Решето Эратосфена #9
fasked, просто есть теорема в теории чисел, что достаточно бежать до http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}, когда вычеркиваем элементы, кратные 2, 3,..., http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}. При этом при вычеркивании элементов кратных k, целесообразнее шаг тоже сделать k.
Yandex
Объявления
30.11.2011, 16:15     Решето Эратосфена
Ответ Создать тему
Опции темы

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