Команда Learn2Code - 30.05.2020 - Освіта
У попередньому блозі ми мали справу з простими числами. Ми показали зразок програми, яка визнала, чи є введене число простим чи ні. Сьогодні я хотів би на конкретному прикладі показати вам, як субтитри цього блогу це вирішують, і таким чином з’ясувати прості числа на визначеному інтервалі натуральних чисел, тоді як верхня межа інтервалу буде введена користувач. Нижня межа інтервалу буде дорівнювати 0, що, звичайно, не є простим числом, оскільки просте число ділиться на число 1 і саме на себе. Звідси випливає, що 0, хоча і ділиться на 1, не ділиться на 0, оскільки вираз 0/0 не визначений. Хоча можна подумати, що результат може дорівнювати цифрі 1, це не так. Нуль просто не може розділити жоден вираз.
Зараз підемо трохи далі. В останньому блозі я дійшов висновку, що навіть 1 не є простим числом, тому що воно ділиться на 1 і саме на себе, що знову є числом 1. І 1 і 1, немає двох різних факторів.
Умова, яка виключає 0 і 1, не є простими числами, звичайно, розглядається в моїй програмі. Але як щодо інших чисел, які знаходяться на інтервалі, верхню межу якого ввів користувач. Простий алгоритм, який називається сито Ератостен, дасть нам пряму відповідь на це питання.
Ератосфен Кіренський, серед іншого, був грецьким математиком, який працював у Стародавній Олександрії близько 280 років. до Різдва Христового. На додаток до обчислення периметра Землі, він також визначив алгоритм, який я реалізував для вас на мові програмування вищого рівня C++.
Перш ніж детально проаналізувати програму, написану на C ++, ми покажемо алгоритм на таких натуральних числах: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Отже, ми маємо послідовність, яка на початку визначається числом 0 включно, а в кінці числом 20, яке вже знаходиться поза інтервалом послідовності. І це саме верхня межа, про яку було сказано вище.
Ми помістимо цю послідовність в однорядкову таблицю, яка в моїй програмі буде представлена вектором цілих чисел (int vector).
Як зауваження, ми будемо використовувати клас бібліотеки STL, який є вектором. Вектор - це сутність, якою краще маніпулювати, ніж масивом. Саме тому ця стаття призначена для тих читачів, які хоча б дещо знайомі з проблемою векторів. Для тих, хто не знайомий з проблемами вектора, я рекомендую спочатку вивчити тип size_t, векторний клас та метод-член векторного класу push_back (). Потім із завзяттям ці читачі можуть розпочати цей блог.
Але повернемось до нашої визначеної проблеми. Тож давайте згадану послідовність:
У цій таблиці ми позначимо синім кольором той факт, що 0 і 1 не є простими числами:
Тому ми не будемо повертатися до індексів, на яких розташовані числа 0 та 1. Давайте подивимось на число 2. Ми знаємо, що це число є найменшим простим числом у цьому інтервалі, що є головною умовою для нас, щоб вирішити субтитри цього блогу. Інші елементи (цифри) послідовності ми перевіримо ситом Ератостен - тобто тепер видалимо кратні числа 2. Оскільки число 3 не кратне числу 2, воно пройде через сито Ератостен . Тож давайте запишемо в таблицю кратні числа 2 червоним кольором.
Ми бачимо, що за один крок алгоритм (сито Ератостен) видалив числа 4, 6, 8, 10, 12, 14, 16 і 18. При цьому ми ніяк не повернемося до індексу числа 2. З попередньої таблиці також очевидно, що число 3 є простим числом. Давайте тепер видалимо його кратні зі таблиці та позначимо цей факт зеленим кольором.
На наступному кроці алгоритм видалив числа 6, 9, 12, 15, 18, які не є простими числами. Так, ми також позначили зеленим кольором деякі цифри, які були видалені на попередньому кроці кратним 2. Однак це не змінює того факту, що цей крок видалив інші числа з послідовності, які є цифрами: 9 і 15. Після виконуючи згаданий крок, ми бачимо, що цифра 5 залишилася позначеною жовтим кольором. Отже, число 5 є простим числом, оскільки воно пройшло через сито Ератостен. Якщо ми видалимо кратні числа 5 на наступному кроці, ми виявимо, що числа 10 і 15 вже були вилучені кратним іншому числу. То коли закінчиться алгоритм? Так буде до тих пір, поки насправді не дійдемо до числа 19. Число 19 більше не має завдання видалити будь-яке кратне, оскільки в нашій таблиці за ними немає нічого. Досягнення його індексу за допомогою певної змінної взаємодії є умовою закінчення алгоритму, хоча ніщо не змінює стан простих чи видалених чисел.
Давайте тепер виберемо з нашої таблиці всі цифри, позначені жовтим:
У нас залишаться числа, які, безумовно, є простими числами. Отже, ми дійшли до результату нашого алгоритму - це числа 2, 3, 5, 7, 11, 13, 17 і 19. Для перевірки ви можете порівняти ці числа з простими числами, наведеними в інших джерелах, але однозначно отримати той самий результат.
Давайте тепер детально розберемо наступний вихідний код, написаний на C ++, який є реалізацією словесного пояснення згаданого вище алгоритму. Мова С ++ пропонує нам інші можливості, як зробити обчислення більш ефективним. Вони, наприклад, стрибки в програмі, яку ми можемо виконати за допомогою ключових слів break і продовжити. Але про це пізніше. Давайте наведемо порядок з першого рядка.
У рядку 1 у нас є файл заголовка iostream.h, доданий директивою препроцесора. Це означає, що вміст файлу iostream.h вставляється в цей рядок. Подібним чином у рядки 2 і 3 ми вставляємо файли заголовків vector.h та string.h з тією ж директивою. Рядок 4 декларує, що ми використовуватимемо простір імен std у всьому вихідному коді, який складає один файл, тому нам не потрібно явно викликати його в основній функції, коли нам потрібен клас або об’єкт з нього. Прикладом може бути об'єкт cin або cout. У рядку 6 визначаємо функцію main, а потім у рядку 7 починається її тіло. У рядку 8 ми оголошуємо змінну цілого типу, зокрема char з ідентифікатором змінної c_end. Ця змінна представляє один символ, який вирішує, припиняти зовнішній цикл чи ні після виконання власного алгоритму Ератостена. Ось чому в рядку 89 користувачеві пропонується натиснути клавішу a або n. Якщо він придушує n, програма продовжує наступний цикл циклу while. Якщо натиснути іншу клавішу, програма закінчується.
Рядок 9 визначає новий екземпляр рядка класу з ідентифікатором sz, який ініціалізується до порожнього значення.
Після цієї ініціалізації в рядку 10 відображається оголошення змінної iSZ типу int без подальшої ініціалізації.
У рядку 11 ми оголошуємо змінну типу bool, яка буде зберігати інформацію в програмі, чи відповідав користувач на запит програми, ввівши дійсне значення (тобто ціле число), яке буде зберігатися у змінній iSZ. Якщо користувач вводить дійсну вхідну інформацію з вікна програми консолі, для змінної is_size_t встановлюється значення true, інакше (якщо користувач не вводить дійсне значення з цілого діапазону) для змінної is_size_t встановлюється значення false. Змінна is_size_t спочатку ініціалізується значенням false у рядку. Це являє собою стан, що змінна iSZ ще не ініціалізована, і це насправді відповідає дійсності. У рядку 13 показано ключове слово до. Це означає, що тіло циклу починається з деякого часу, в якому умовою є порівняння вмісту змінної c_end із символом n (див. Рядок 95).
Коли програма продовжується, вона потрапляє до рядка 14, який через деякий час відкриває тіло згаданого циклу, за яким слідує цикл while на рядку 15, що означає цикл із умовою на початку кожного циклу. Саме тут програма запитує (порівнює), чи зберігається значення false у змінній. Якщо так, програма продовжує позитивне відгалуження та пропонує рядку 17 користувачеві ввести верхню межу сита Eratosten. Це значення не буде враховано при тестуванні простого числа. У рядку 18 введені користувачем дані завантажуються у змінну (об'єкт) sz, яка є новим екземпляром класу рядків. Завантаження виконується за допомогою методу getline (), який має два параметри, а саме об’єкт cin та об’єкт sz.
За рядком 20 слідує блог try and catch code, який використовується для розпізнавання дійсності значення, введеного користувачем в об’єкт sz. У гілці try програма намагається перетворити значення в об'єкті sz на ціле число, яке представляє довжину інтервалу, на якому ми шукаємо всі прості числа через сито Ератостен. Для цього перетворення використовується функція stoi, яка коротше означає рядок у ціле число (у словацькій мові рядок у ціле число). Після перетворення в рядку 24 перевіряється, чи не ввів користувач на введенні число 0. Якщо так, програма встановлює змінну is_size_t на false і переходить до переоцінених умов наступного циклу while, використовуючи продовжити заяву. Оскільки змінна is_size_t знову хибна, програма продовжує цикл while, коли в рядку 17 користувачеві знову пропонується ввести верхню межу інтервалу сита Eratosten. Таким чином, програму можна циклювати, доки користувач не введе дійсне значення на вході консольної програми.
Давайте розглянемо тепер, коли користувач не вводить значення з інтегрального діапазону типів (наприклад, недійсне значення "hsfu"). Напевно, ви вже знаєте, що це не цілісне значення типу, а безглузді символи, які користувач може ввести, оскільки ці значення можна присвоїти типу рядка, але це значення не можна перетворити на ціле значення. Ось чому в нашій програмі є блок catch у рядку 34, який вловлює цей виняток. А що насправді буде далі? Але так само, як і у випадку введення 0, це означає, що для значення false встановлюється змінна is_size_t і програма перескакує з оператором continue на початок циклу while, де воно знову обчислюється в умові, чи продовжувати запропонувавши користувачеві ввести дійсне значення верхньої межі. Решето Ератостена, а оскільки заперечення значення у змінній is_size_t є істинним, програма все одно зробить це. І тому програма запропонує користувачеві навколо ввести дійсне значення.
Якщо користувач вводить дійсне значення, програма переходить до гілки try, де потім переходить до від'ємної гілки оператора if (клавіша else у рядку 29), де для значення is_size_t вже встановлено значення true. Таким чином, у цьому циклі програма вискакує з циклів while, оскільки вона більше не задовольняє умові наступного виконання циклу.
Коли користувач вводить дійсну верхню межу сита Eratosten, цю інформацію можна використовувати для виділення вектора довжини iSZ (розподіл векторів з ідентифікатором vNumberVector), який реалізований у рядку 41. У рядку 42 виділено вектор довжиною 0 (вектор з ідентифікатором vPrimeVektor). У цьому векторі ми будемо зберігати прості числа, які проходять через сито Ератостен. Вектор має довжину 0, оскільки можна додати просте число після нього лише тоді, коли частина алгоритму приймає рішення, чи є число, вибране з вектора vNumberVector, простим числом чи ні.
У рядку 44 починається цикл for, який у своїх окремих циклах управляється ітераційною змінною i, яка збільшується в кожному циклі, поки не досягне значення iSZ. Цикл for у своєму тілі заповнює вектор vNumberVector числами від 0 до 19 (оскільки верхня межа, яку ми визначили в прикладі, становить 20).
Якщо залишок після ділення дорівнює нулю, тестоване число не є простим числом, що означає, що ми встановлюємо для змінної прапора значення false, ми переходимо до кінця циклу for, використовуючи ключове слово break (ітераційна змінна j). У цьому випадку ніщо не зберігається у векторі vPrimeVector, оскільки змінна значення зберігається у змінній прапора. зовнішній цикл for завершується, коли перевіряються всі числа, збережені у векторі vNumberVector. Останнє тестоване число - це число 19.
Після тестування всіх чисел прості числа записуються у вікно програми консолі (див. Рядки 78-83), для чого ми використовуємо об'єкт cout та цикл for. Звичайно, запис також включає переміщення курсору до нового рядка на рядку 85.
Потім у вікні програми консолі пишеться підказка, щоб запитати користувача, хоче він вийти з програми чи ні. Якщо користувач натискає клавішу n, програма продовжується, і користувачеві пропонується повторно ввести верхню межу сита Eratosten, при цьому значення is_s знову зберігається false.
Якщо користувач пригнічує іншу клавішу (що означає припинення програми), програма переходить після зовнішнього циклу while до рядка 97, основна функція повертає 0 в операційну систему, і вся програма завершується. Я нагадую вам, що у рядку 98 є права програмна дужка, яка закриває тіло основної функції.
Перелік програм main.cpp
Вікно програми консолі на верхній межі сита Eratosten 20
На малюнку видно, що отримані прості числа збігаються з простими числами, які ми розрахували аналітично (див. Останню таблицю в тексті).
Сподіваюсь, вас зацікавив приклад і програма з ситом Eratosten, вам потрібно лише впровадити його на свій комп.
Цей блог написав Марек ШУРКА, викладач курсів C ++. Якщо у вас є питання, напишіть їх у коментарях.
Ми вчимо людей проектувати, створювати веб-сайти та програмувати. Ви можете знайти наші денні курси в кількох містах Словаччини, а за допомогою онлайн-курсів ви можете навчитися, не виходячи з дому.