Задача
По заданным числам $a$ и $b$ вывести все простые числа в интервале от $a$ до $b$ включительно.
Входные данные
Два числа $a$ и $b \ (1 \leqslant a \leqslant b \leqslant 100000)$.
Выходные данные
Вывести в одной строке все простые числа в интервале от $a$ до $b$ включительно.
Тесты
| № | Входные данные | Выходные данные | Объяснение |
| 1 | 2 2 | 2 | |
| 2 | 1 100 | 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 | |
| 3 | 50 100 | 53 59 61 67 71 73 79 83 89 97 | |
| 4 | 10 2 | Неправильно, так как противоречит условию ($a \leqslant b$) | |
| 5 | 99900 100000 | 99901 99907 99923 99929 99961 99971 99989 99991 | |
| 6 | -15 -6 | -13 -11 -7 | Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$) |
Код
|
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 |
#include <iostream> #include <cmath> using namespace std; bool eratosthenesSieve(int currentNumber) { /* Describe the function that checks if the number is prime and returns a boolean value. This function is based on the "sieve of Eratosthenes" algorithm. True - if the number is prime, false - normal. */ // If the number equals to 1 or if it even, return false. And if it equals to 2, return true. if (currentNumber == 2 or currentNumber == 3) { return true; } else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) { return false; } // If the number has the divider from 5 to the root of this number with the second step return false. for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) { if (!(currentNumber % divider)) { return false; } } // In all other situations, return true. return true; } void printSequenceOfPrimeNumbers(int beginning, int ending) { /* This function prints all prime numbers in a line. It contains a loop that starts and ends with the given values. */ for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) { if (eratosthenesSieve(sequenceElement)) { cout << sequenceElement << " "; } } } int main() { /* Receive the beginning and end of the sequence. */ int beginning, ending; cin >> beginning >> ending; // Calling the function. printSequenceOfPrimeNumbers(beginning, ending); return 0; } |
Решение
Решето Эратосфена это алгоритм поиска простых чисел.
Решение данной задачи сводится к тому, чтобы воплотить данный алгоритм. По мере прохождения перечня, нужные числа остаются, а ненужные (составные) исключаются.
Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.
Рассуждение:
— Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
— Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
— Число $4$ уже выбыло из игры, так как делится на $2$.
— Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
— Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.
В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.
Таким же образом, проверяем все остальные числа из промежутка от $n$ до $m$ и выводим полученную последовательность на экран.
— При первом упоминании простого числа должна быть ссылка на статью Википедии о них.
— «В примере указанном выше» — это вы про код своего решения задачи? Может так и написать?
— Как только добавите ссылку, прочитайте саму статью и добавьте один важный тест, который показывает, что Ваша программа содержит ошибку и иногда печатает не простые числа. Исправьте программу.
— Пожалуйста, после описания решета Эратосфена, явно укажите, что Ваше решение не имеет к нему никакого отношения. А еще лучше просто дайте ссылку на его описание в Википедии. Но написать, что Вы им не пользуетесь нужно обязательно.
— Решение я принимаю, но это самое неэффективное решение из всех, что я видел. Вы даже не делаете попытки исключить проверку деления на четные числа если не разделилось на два. Одно это уже ускорило бы программу в два раза.
— Почему у Вас обезьянка вместо аватарки?
— Меток не указали.
— Указали несколько взаимоисключающих категорий. Делаю вывод, вы не знаете, что мы называем линейными вычислениями.
Подскажите, пожалуйста. Ссылку на статью о простых числах нужно указать непосредственно в категории «Ссылки» или в «Решении»?
Исправил замечания.