Вернуться на Страничку новостей.

27.12.2008

Решето Эратосфена
Программа выводит ряд простых чисел в интервале от 0 до 50.
За основу взята программа на тему "Поиск в строках"
глава 3 из книги "Thinking in C++" -Автор Брюс Эккель.

Интересная программа, я бы даже сказал забавная!
Оригинальное решение и оригинальная демонстрация
применения find() и find_first_not_of().
И применения алгоритма "просеивания" простых чисел - "Решето Эратосфена".


//: C03:Sieve.h
#ifndef SIEVE_H
#define SIEVE_H
#include <cmath>
#include <string>
#include <iostream>
using namespace std;

class SieveTest {

string sieveChars;
public:
// Создание строки длиной 50 и заполнение ее символов
// значениями 'P' (сокращение от Prime, то есть "простое число")
SieveTest() : sieveChars(50, 'P') {}

void run() {

findPrimes();
testPrimes();
}

bool isPrime (int p) {

if (p == 0 || p == 1) return false;
int root = int(sqrt(double(p)));
for (int i = 2; i <= root; ++i)
if (p % i == 0)
return false;
return true;
}

void findPrimes () {

// По определению числа 0 и 1 не являются простыми.
// Заменяем эти элементы символами "N".
sieveChars.replace(0, 2, "NN");
cout << sieveChars << endl;

// Перебор массива:
size_t sieveSize = sieveChars.size();
int root = int(sqrt(double(sieveSize)));

for (int i = 2; i <= root; ++i){

// Поиск всех кратных чисел:
// В позицию строки, соответствующую кратному числу
// вставим символ 'N'
for (size_t factor = 2; factor * i < sieveSize; ++factor){
sieveChars[factor * i] = 'N';
}
}
cout << sieveChars << endl;
}

void testPrimes () {

size_t i = sieveChars.find('P');
while (i != string::npos) {
i = sieveChars.find('P', i);
cout << i << endl;
i++;
i++;
if(i >= 48) break;
}
cout << " OK !" << endl;

i = sieveChars.find_first_not_of('P');
while (i != string::npos) {

i = sieveChars.find_first_not_of('P', i);
cout << i << endl;
i++;
i++;
if(i >= 48) break;
}
}
};
#endif // SIEVE_H ///:~

//: C03:Sieve.cpp
#include "Sieve.h"

int main() {

SieveTest t;
t.run();

char StopCharacter;
cout << endl << "Press a key and \"Enter\" : ";
cin >> StopCharacter;

return 0;

} ///:~

Результат:


NNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !

Анализ:

В следующей строке все символы 'P' находятся на позициях,
на которых находятся в последовательности натуральных чисел простые числа.

NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN

Теперь ничего не стоит вывести и сами числа.

А решето Эратосфена действует замечательно! Оно пометило все простые числа символом 'P'.
Точнее говоря пометило все непростые числа символом 'N'.
И сделала это функция findPrimes().

Для начала в программе создадим строку в 50 символов и заполним ее символами 'P'.
Для этого в программе сначала сделано объявление строки, а затем ее инициализация символами 'P'. Причем инициализация строки сделана в конструкторе класса SieveTest:

class SieveTest {

string sieveChars;
public:
// Создание строки длиной 50 и заполнение ее символов
// значениями 'P' (сокращение от Prime, то есть "простое число")
SieveTest() : sieveChars(50, 'P') {}

...

Надо сказать, что объявление а затем инициализация строки символами в конструкторе класса - весьма любопытна.
Благодаря такой инициализации можно обращаться со строкой как как с массивом символов. Что далее мы и увидим.

void findPrimes () {

// По определению числа 0 и 1 не являются простыми.
// Заменяем эти элементы символами "N".
sieveChars.replace(0, 2, "NN");
cout << sieveChars << endl;

// Перебор массива:
size_t sieveSize = sieveChars.size();
int root = int(sqrt(double(sieveSize)));

for (int i = 2; i <= root; ++i){

// Поиск всех кратных чисел:
// В позицию строки, соответствующую кратному числу
// вставим символ 'N'
for (size_t factor = 2; factor * i < sieveSize; ++factor){
sieveChars[factor * i] = 'N';
}
}
cout << sieveChars << endl;
}

Эта функция в двойном цикле определила все значения позиций, которые соответствуют непростым числам. Во все эти позиции функция поместила символ 'N'. В остальных позициях строки остался символ 'P'. То есть символ 'P' остался только в тех позициях, значение которых соответствует простым числам в интервале от 0 до 50.

Вот что сделала эта функция! Это и есть работа алгоритма, называемого Решето Эратосфена.

Подсказка

Эта функция преобразовала строку, состоящую из одних только символов 'P',
в строку в которой все символы 'P' находятся на позициях, на которых находятся в
последовательности натуральных чисел простые числа.

Меня удивила следующая инструкция:

sieveChars[factor * i] = 'N';

Просто я не знал(!), что можно в строке посимвольно так изменять составляющие ее символы.
Надо проверить эту инструкцию в других программах.

Просто я упустил из виду, что в конструкторе класса SieveTest создается и инициализируется
массив символов на 50 элементов:

SieveTest() : sieveChars(50, 'P') {}

Далее этот массив символов будет использоваться.

Итак строка сформирована. В ней в позиции простых чисел находятся символы 'P'

В следующей функции testPrimes () при помощи find() будем находить позиции, в которых находятся символы 'P'. Значения этих позиций будут совпадать со значениями простых чисел. Таким образом мы имеем возможность вывести простые числа в интервале от 0 до 50 !

void testPrimes () {

size_t i = sieveChars.find('P');
while (i != string::npos) {
i = sieveChars.find('P', i);
cout << i << endl;
i++;
i++;
if(i >= 48) break;
}
cout << " OK !" << endl;
};

Функция выводит следующую последовательность простых чисел:
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !

Интересная программа! Оригинальное решение и оригинальная демонстрация
применения find(). И применения алгоритма "Решето Эратосфена".

Для того, чтобы вывести все непростые числа в том же интервале,
достаточно в функции testPrimes() добавить тот же код, который уже был написан, но в нем заменить find() на find_first_not_of():

void testPrimes () {

size_t i = sieveChars.find('P');
while (i != string::npos) {
i = sieveChars.find('P', i);
cout << i << endl;
i++;
i++;
if(i >= 48) break;
}
cout << " OK !" << endl;

i = sieveChars.find_first_not_of('P');
while (i != string::npos) {

i = sieveChars.find_first_not_of('P', i);
cout << i << endl;
i++;
i++;
if(i >= 48) break;
}
}
};

Примечание: Почемуто в программе не работает условие выхода из цикла:

while (i != string::npos)

Поэтому в конце каждого цикла мне пришлось добавить инструкцию:

if(i >= 48) break;

Результат:

NNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !
0
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46

Hosted by uCoz