ООП для Заоч / Пинчук Лозовская Программир на С
13.3. Пошук простих чисел. Решето Ератосфена
Задача
Надано число N0. Добути всі прості числа, що не перевищують N.
Алгоритм
Алгоритм, відомий як "Решето Ератосфена", базується на послідовному викреслюванні з ряду натуральних чисел, спочатку парних чисел, далі чисел, які діляться без залишку на 3, на 4, і т. д. Наведена нижче програма по заданому значенню N знаходить всі прості числа з інтервалу [0..N] та підраховує їх кількість. Тут M - верхня оцінка кількості простих чисел на інтервалі [0..N], m - фактична кількість простих чисел з цього інтервалу. У програмі використовується відома формула для отримання оцінки M:
// Приклад 1
#include <syst.h>
Содержание
- Запоріжжя знту 2008
- Глава 1
- 1.1. Історія та сучасність
- 1.2. Загальна структура програми. Два простих приклади
- Void main()
- Void main()
- Глава 2 Об’єкти та ідентифікатори
- 2.1. Об'єкти та їхні атрибути
- 2.2. Алфавіт мови та лексеми
- 2.3. Ідентифікатори
- Void main() // (рівень 0)
- 2.4. Вправи
- Глава 3
- 3.1. Поняття виразу. Вирази Lvalue та Rvalue
- 3.2. Операції. Пріоритети та асоціативність
- Void main()
- Void main()
- Void main()
- 3.3. Вправи
- Глава 4
- 4.1. Види операторів
- 4.2. Стандартні оператори
- If (лв) опер_1; [ else опер_2; ]
- Void main()
- If (лв1) опер_1;
- Void main()
- Void main()
- Void main()
- Void main()
- Void main()
- 4.3. Оголошення змінних та ініціалізація
- Int number(125);
- Int number(125);
- 4.4. Константи і константні об'єкти
- Void main()
- 4.5. Вправи
- Глава 5
- 5.1. Типи та їхні різновиди
- 5.2. Службове слово void
- Int a[small], a[large];
- 5.4. Перетворення типів
- 5.5. Вправи
- Void main()
- Глава 6 покажчики і посилання
- 6.1. Покажчики
- Void main()
- Void strcpy(char* s1, char* s2)
- Void* pv;
- 6.2. Посилання
- 6.3 Вправи
- Void main()
- Глава 7 масиви і динамічні об'єкти
- 7.1. Масиви
- Void main()
- 7.2. Рядки символів
- Int strlen(char* s);
- Int strcmp(char* s1, char* s2);
- Int len(char *s)
- 7.3. Динамічні об'єкти й масиви
- Void main()
- Void main()
- Void main()
- Void main()
- 7.4. Вправи
- Глава 8 функції та процедури
- 8.1. Загальні відомості
- Void main()
- Void c_mul(double a_re, double a_im,
- Void swap1(long *px, long *py)
- Void swap2(long &X, long &y)
- Void main()
- Int fun(int, float*, double&);
- Void fun(int n)
- Void main()
- Void swap(int& a, int& b)
- 8.2. Функція main
- Void або int main(int n, char** p, char** q);
- Void main(int n, char** p, char** q)
- 8.3. Функції зі змінною кількістю параметрів
- Void main()
- 8.4. Покажчики на функції
- Int (*pf[3])(float X, float y);
- Void main()
- 8.5. Функції з шаблонами
- Void swap(string& s1, string& s2)
- Void main()
- Inline t abs(t X)
- Void create(type* &a, int n)
- Void del(type* &a)
- 8.6. Вправи
- Глава 9 консольне вВедення / вИведення
- 9.1. Засоби бібліотеки с
- Void main()
- Void main()
- Void main()
- 9.2. Використання потоків
- Void main()
- Void main()
- 9.3. Вправи
- Глава 10 операції з файлами
- 10.1. Види файлів і режими роботи з ними
- 10.2. Бібліотека с
- Void fprint(file* f, &X)
- Void rewind(file* f);
- Void main()
- Void main(int n, char** f)
- Void main(int n, char** fnam)
- 10.3. Застосування потоків
- Ifstream fin;
- Void open(char* filename, int mode, int access);
- Ifstream fin("a.Dat");
- Void main()
- Ifstream fa("a.Dat");
- If (fa.Eof()) break;
- Void main(int n, char** fnam)
- Void main(int n, char** f)
- Ifstream fa(f[1]);
- Void main(int n, char** fnam)
- Void main()
- Ifstream in("example.Cpp");
- Void main()
- Ifstream in("name.Dat",ios::binary);
- Void main()
- Ifstream fa("a.Dat");
- Int descr(fstr& f)
- Void main()
- Ifstream ina(infa);
- Ifstream inb(infb);
- 10.4. Вправи
- Глава 11 компіляція програми. Директиви і макроси
- 11.1. Фази компіляції
- 11.2. Директиви режиму компіляції
- 11.3. Директиви препроцесора
- 11.4. Вправи
- Глава 12 змішане програмування. Використання ассемблерного коду
- 12.1. Засоби використання асемблера
- Void main()
- 12.2. Вправи
- Глава 13 програмна реалізація алгоритмів
- 13.1. Алгоритм Евкліда пошуку найбільшого загального дільника двох цілих чисел
- 13.2. Обчислення факторіала
- 13.3. Пошук простих чисел. Решето Ератосфена
- Void main()
- 13.4. Генерація підмножин
- Void main()
- 13.5. Сортування масивів
- Void main()
- Void main()
- Int flag;
- 13.6. Пошук у масиві
- Void main()
- Void main()
- 13.7. Операції з матрицями
- Void ObrMatr (double** a, double** b, unsigned n )
- Void Minv(double** a, double** b, unsigned n )
- Void Gauss(double** a, double* b, double* X, unsigned n)
- 13.8. Лінійна інтерполяція даних
- 13.9. Лінійна апроксимація
- Void linappr(int n, double* X, double* y, double& a0, double& a1)
- 13.10. Розв’язування нелінійних рівнянь
- Void Bisec(funx f, double a, double b, double eps, double& X)
- Void Bisec(funx f, double a, double b,
- Void main()
- 13.11. Пошук заданої послідовності символів у файлі
- Void push(char* s, int n, char X)
- Void main()
- 13.12. Вправи
- Глава 14 створення й використання бібліотечних модулів. Модуль syst.H
- 14.1. Створення бібліотечних модулів
- 14.2. Модуль syst.H
- 14.3. Системні функції та макрооперації
- Void runtimer();
- Void main()
- Void runstimer();
- Void main()
- Void swp(Type& a, Type& b);
- Void main()
- Int cmp(int nx, int ny, Type* X, Type* y);
- Void errhalt(bool ex, char* mes);
- Void errhalt(bool ex, char* mes, file* f);
- 14.4. Операції введення/виведення
- Void flushkey();
- Void main()
- Int getyes();
- Void main()
- Void main()
- Int weight(type X);
- Void main()
- Int hamdist(Type a, Type b)
- 14.6. Спеціальні класи. Клас Spline для інтерполяції даних сплайнами
- Void main()
- 14.7. Вправи
- Глава 15 графІчне виведення. Модуль rgraph.H
- 15.1. Модуль rgraph.H. Загальні відомості
- 15.2. Глобальні змінні й константи
- 15.3. Класи й покажчики на функції
- 15.4. Функції й процедури класів
- Void main()
- Void main()
- Void main()
- Void main()
- 15.7. Вправи
- Глава 16 Життєвий цикл програмного продукту. Питання стилю запису програм
- 16.1. Життєвий цикл програми
- Int n, alfa, col;
- Void draw();
- Void rotate(int delta);
- 16.3. Вправи
- Література