С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
o33ik
138 / 5 / 1
Регистрация: 25.03.2013
Сообщений: 228
#1

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

16.09.2013, 21:18. Просмотров 602. Ответов 8
Метки нет (Все метки)

Дали код алгоритма Ератосфена для поиска простых чисел, надо в нем разобраться, знать как все работает и т.п. И как я начал разчихлять код, то сразу и стал на побитовых операциях. Понял только bits[n >> 3] и все... Кому не сложно, обьясните мне етот код коментарями около строчек в классе bitset, а если не сложно то и весь код, а то времени мало, а лабу надо здать. И немогу понять толком код. Наперед спасибо
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <ctime>
 
using namespace std;
 
template<int N>
 
class bitset
{
private:
   char* bits;
public:
    bitset() : bits(new char[(N - 1) / 8 + 1]){}
    bool test(int n) 
    { 
        return (bits[n >> 3] & (1 << (n & 7))) != 0; 
    }
    void set(int n) 
    { 
        bits[n >> 3] |= 1 << (n & 7); 
    }
    void reset(int n) 
    { 
        bits[n >> 3] &= ~(1 << (n & 7));
    }
};
 
int main()
{ 
   const long N = 10000000;
   clock_t cstart = clock();
   bitset<N + 1> b;
   int count = 0;
   int i;
   for (i = 2; i <= N; i++)
      b.set(i);
   i = 2;
   while (i * i <= N)
   { 
      if (b.test(i))
      { 
         count++;
         int k = 2 * i;
         while (k <= N)
         { 
             b.reset(k);
             k += i;
         }
      }
      i++;
   }
   
   while (i <= N)
   {
      if (b.test(i))
         count++;
      i++;
   }
 
   clock_t cend = clock();
   double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;
 
   cout << count << " primes\n" << millis << " milliseconds\n";
   system("pause");
   return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2013, 21:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Решето Ератосфена (C++):

Решето Эратосфена - C++
Простое число — это любое целое число, которое точно делится без остатка только само на себя и на 1. Решето Эратосфена — это способ...

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

Решето Эратосфена - C++
Возможно ли найти простые числа методом решета Эратосфена с помощью вектора за один проход? Добавлено через 1 минуту У меня...

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

Решето Эратосфена - C++
Как можно реализовать? Подскажите плиз

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

8
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,254
16.09.2013, 21:39 #2
ну вот например
Цитата Сообщение от o33ik Посмотреть сообщение
bool test(int n)
* * {
* * * * return (bits[n >> 3] & (1 << (n & 7))) != 0;
* * }
в одном байте у тебя упаковано 8 бит
надо например проверить 20
в каком байте он лежит ?
20/8=2 значит в третьем(отсчет идет с 0)
n >> 3 это и есть делить на 8
берем это байт из массива
bits[n >> 3] получится bits[2]
там лежит 8 бит какой нам нужен?
берем остаток от деления на 8
20%8=4 (пятый бит отсчет тоже от 0)
n & 7 это остаток деления на 8
допустим там 1 вот так выглядит байт ххх1хххх(х это безразлично какое значение)
берем 1 сдвигаем её на 4
1 << (n & 7)) получаем 00010000
потом это число и байт производим операцию "И" (выделяем бит)
х х х 1 х х х х
0 0 0 1 0 0 0 0
-----------------
0 0 0 1 0 0 0 0
полученное число сравниваем с 0
0 0 0 1 0 0 0 0 не равно 0? да(true)
возвращаем true
вот так можно переписать эту функцию
C++
1
2
3
4
5
6
7
8
9
10
bool test(int n) 
{ 
 int tmp1=n/8;
 int tmp2=n%8;
 unsigned char bt1=bits[tmp1];
 unsigned char bt2=0x01<<tmp2;
 unsigned char bt3=bt1&bt2;
 bool bl=bt3!=0;
 return bl;
}
так более понятно?
1
o33ik
138 / 5 / 1
Регистрация: 25.03.2013
Сообщений: 228
16.09.2013, 21:56  [ТС] #3
ValeryS, да, теперь более понятно. спасибо
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
16.09.2013, 22:16 #4
o33ik, Могу еще тебе с алгоритмом помочь если не знаешь, в общем допустим ты хочешь из 1000 чисел найти все простые, записывай эти все числа в массив из ста элементов допустим int mass[1000] и просто удаляешь из этого массива все не простые числа, от например один простое число, два простое число в массиве оставляешь два допустим равный один, берешь два умножаешь на 2 получается 4 элемент mass[4] устанавливаешь в 0 потом 2*2*2 получается 8 элеменет mass[8] устанавливаешь в 0 и так пока 2*2 * .. не будет больше 1000, потом берешь следующее простое число 3, и удаляешь из массива все множетели 3*3 пото 3*3*3 и так далее 4 уже не возьмешь потому что оно уже в 0 установлено берешь 5 для пяти удаляешь, 6 тоже не возьмешь. Короче таким макаром удаляешь из массива все не простые числа и у тебя в массиве остается только простые числа.
0
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,254
16.09.2013, 22:27 #5
ninja2,
так у него по моему так и сделано
только вместо массива битовое поле
Цитата Сообщение от o33ik Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (i * i <= N)
  { 
   if (b.test(i))
    { 
    count++;
      int k = 2 * i;
        while (k <= N)
        { 
           b.reset(k);
           k += i;
         }
      }
    i++;
  }
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
16.09.2013, 23:10 #6
ValeryS, Да я его код не смотрел, просто алгоритм помню.

Добавлено через 57 секунд
Он может код видит, а что он делает не понимает.
0
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
17.09.2013, 03:05 #7
Цитата Сообщение от ninja2 Посмотреть сообщение
Он может код видит, а что он делает не понимает.
Ваше объяснение... Простите. Лучше википедия!

P.S. Гифборду из форума не сделать =)
0
Миниатюры
Решето Ератосфена  
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
17.09.2013, 12:34 #8
Цитата Сообщение от o33ik Посмотреть сообщение
обьясните мне етот код коментарями около строчек в классе bitset
Зачем тебе этот bitset, когда в Си++ есть стандартный?

Добавлено через 1 минуту
Если чтобы быстрее работал, то в память вполне влезет обычный массив.
0
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
17.09.2013, 17:43 #9
Цитата Сообщение от Qwertiy Посмотреть сообщение
Зачем тебе этот bitset, когда в Си++ есть стандартный?
Скорее всего, банально потому, что "так надо по лабе".
0
17.09.2013, 17:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.09.2013, 17:43
Привет! Вот еще темы с ответами:

Решето Эратосфена - C++
В решете эратосфена из книги в условии есть непонятная вещь: if (i * 1ll * i &lt;= n) - возле единицы для непонятных знака, на форуме они...

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

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

Решето Эрастосфена - C++
В С++ создать решето Эрастосфена, в зависимости от параметров запуска, программа или графически отображает весь процесс (при маленьких...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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