Рубрики

Вывести простые числа в заданном диапазоне, используя C ++ STL

Генерация всех простых чисел между двумя данными числами. Задача состоит в том, чтобы напечатать простые числа в этом диапазоне. Сито Эратосфена является одним из наиболее эффективных способов найти все простые числа меньше n, где n меньше 10 миллионов или около того.

Примеры:

Input : start = 50 end = 100
Output : 53 59 61 67 71 73 79 83 89 97

Input : start = 900 end = 1000
Output : 907 911 919 929 937 941 947 953 967 971 977 983 991 997

Идея состоит в том, чтобы использовать Сито Эратосфена в качестве подпрограммы. Во-первых, найдите простые числа в диапазоне от 0 до начала и сохраните их в векторе. Аналогично найдите простые числа в диапазоне от 0 до конца и сохраните их в другом векторе. Теперь возьмите заданную разницу двух векторов, чтобы получить требуемый ответ. Удалите лишние нули, если таковые имеются в векторе.

// C ++ STL программа для печати всех простых чисел
// в диапазоне с использованием сита эратосфена
#include<bits/stdc++.h>

using namespace std;

  

typedef unsigned long long int ulli;

   
vector<ulli> sieve(ulli n)
{

    // Создаем логический вектор "prime [0..n]" и

    // инициализируем все записи как true. Ценность

    // в простом [i] будет, наконец, ложным, если я

    // Не простое число, иначе верно.

    vector<bool> prime(n+1,true);

       

    prime[0] = false;

    prime[1] = false;

    int m = sqrt(n);

   

    for (ulli p=2; p<=m; p++)

    {

       

        // Если простое число [p] не изменилось, то оно

        // простое число

        if (prime[p])

        {

            // Обновить все кратные р

            for (ulli i=p*2; i<=n; i += p)

            prime[i] = false;

        }

    }

   

    // вставляем все простые числа в вектор ans

    vector<ulli> ans;

    for (int i=0;i<n;i++)

        if (prime[i])

            ans.push_back(i);

    return ans;

}

   
// Используется для удаления нулей из вектора с помощью
// библиотечная функция remove_if ()

bool isZero(ulli i)

{

    return i == 0;

}

   
vector<ulli> sieveRange(ulli start,ulli end)
{

    // найти простые числа из диапазона [0..start]

    vector<ulli> s1 = sieve(start);  

       

    // найти простые числа из диапазона [0..end]

    vector<ulli> s2 = sieve(end);  

   

    vector<ulli> ans(end-start);

       

    // найти заданную разницу двух векторов и

    // выдвигаем результат в вектор ans

    // O (2 * (m + n) -1)

    set_difference(s2.begin(), s2.end(), s1.begin(), 

                             s2.end(), ans.begin());

  

    // удаляем лишние нули, если таковые имеются. На)

    vector<ulli>::iterator itr =

                    remove_if(ans.begin(),ans.end(),isZero);

   

    // изменить его размер // O (n)

    ans.resize(itr-ans.begin());

   

    return ans;

}

   
// Программа драйвера для проверки вышеуказанной функции

int main(void)

    ulli start = 50;

    ulli end = 100;

    vector<ulli> ans = sieveRange(start,end);

    for (auto i:ans)

        cout<<i<<' ';

    return 0;

}

Выход:

53 59 61 67 71 73 79 83 89 97

Эта статья предоставлена Варуном Тхакуром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вывести простые числа в заданном диапазоне, используя C ++ STL

0.00 (0%) 0 votes