Algoholic.in.ua

Решения > Простые числа

Простые числа С++

Категория: Решения | Добавлено: 2015-09-01 | Просмотров: 989

Вывести все простые числа от M до N включительно.


Входные данные.


В первой строке находятся разделённые пробелом M и N (2 ≤ M ≤ N ≤ 300 000).


Выходные данные.


Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent" (без кавычек).


Идея решения:


  1. Воспользуемся решетом Эратосфена для решения данной задачи.
  2. Для того, чтобы алгоритм работал быстрее, игнорируем все чётные числа.

Решение на C++

          #include <iostream>
          #include <vector>

          using namespace std;

          int main()
          {
              //1
              int n,m,am = 0;
              cin >> n >> m;
              vector<bool> prime (m + 1, true);
              prime[0] = prime[1] = false;
              //2
              if(n <= 2){cout << 2 << endl; am++;}
              for (int i = 3; i <= m; i += 2)
                  if (prime[i]){
                      for (int j = 2; i * j <= m; j++)
                          prime[j * i] = false;
                      if(i >= n){
                          cout << i << endl;
                          am++;
                      }
                  }
                  if(am == 0)cout << "Absent" << endl;
              return 0;
          }
        

Пример 1:
Входные данные:
2 5
Выходные данные:
2
3
5
Пример 2:
Входные данные:
4 4
Выходные данные:
Absent


Источник условия:
http://www.e-olymp.com/ru/problems/830


Яндекс.Метрика
Украина онлайн