Новости 028

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