Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
wwmax
0 / 0 / 0
Регистрация: 25.10.2018
Сообщений: 271
1

Найти количество простых чисел в заданном интервале

05.02.2019, 12:31. Просмотров 1270. Ответов 9
Метки нет (Все метки)

По числу n найти количество простых чисел p из интервала n < p < 2n. Нужен быстрый способ.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2019, 12:31
Ответы с готовыми решениями:

Найти количество почти простых чисел в заданном интервале натуральных чисел.
Натуральное число называется почти простым, если оно не простое и имеет только один простой...

Найти количество чисел в интервале от 1 до N, взаимно простых с N
Дано число N. Найти количество чисел в интервале от 1 до N,взаимно простых с N.

Функция вычисления суммы квадратов простых чисел, лежащих в заданном интервале
Составить программу вычисления суммы квадратов простых чисел, лежащих в интервале (M, N).

Найти в заданном одномерном массиве количество простых чисел, используя сортировку простым включением
Помогите, пожалуйста, с решением задач. Тяжело даются динамические массивы. Это должна быть одна...

Определить количество простых чисел в интервале
Определить количество простых чисел в интервале отN до M где N,M-натуальные числа

9
zss
Модератор
Эксперт С++
8617 / 7571 / 4681
Регистрация: 18.12.2011
Сообщений: 20,109
Завершенные тесты: 1
05.02.2019, 13:26 2
См. ссылки внизу страницы
1
Байт
Эксперт C
21305 / 13470 / 2839
Регистрация: 24.12.2010
Сообщений: 28,574
05.02.2019, 14:09 3
Цитата Сообщение от wwmax Посмотреть сообщение
Нужен быстрый способ.
Видимо, какие-то способы тебе известны. И не удовлетворяют по скорости. Чтобы голову нам не ломать, расскажи, какие это способы, и чем они не хороши в твоей ситуации.
1
SomniPhobia
352 / 256 / 101
Регистрация: 22.11.2017
Сообщений: 707
05.02.2019, 14:15 4
wwmax, привет!
Вот код ищёт простые числа от 2 до n.
Реализован алгоритм Решета Эратосфена.
C++
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <numeric>
 
using namespace std;
 
int main()
{
    system("color 0A");
    wcout.imbue(locale("rus_rus.866"));
    
    wcout << L"Введите значение n ";
    size_t n;
    cin >> n;
    auto start = clock();
    vector<bool> v(n + 1u, true);
    v[0u] = false;
    v[1u] = false;
    for (size_t p = 2u; p <= n; ++p)
    {
        for (size_t d = p * p; d <= n; d += p)
        {
            v[d] = false;
        }
    }
    auto finish = clock();
    size_t count = accumulate(v.begin(), v.end(), 0u);
    wcout << L"Количество простых чисел от 2 (включительно) до " << n << L" (включительно) " << count << endl;
 
    wcout << L"На работу алгоритма потрачено секунд "
        << static_cast<double>(finish - start) / CLOCKS_PER_SEC << endl;
 
    /*
    //Вывод простых чисел на консоль
    size_t num = 0u;
    for (const auto &flag : v)
    {
        if (flag)
        {
            cout << num << " ";
        }
        ++num;
    }
    cout << endl;
    */
    
    system("pause");
    return 0;
}
0
Миниатюры
Найти количество простых чисел в заданном интервале  
05.02.2019, 14:15
Байт
Эксперт C
21305 / 13470 / 2839
Регистрация: 24.12.2010
Сообщений: 28,574
05.02.2019, 14:17 5
wwmax, Есть еще формулы приблизительного подсчета. Или тебе нужно точное значение?
0
wwmax
0 / 0 / 0
Регистрация: 25.10.2018
Сообщений: 271
05.02.2019, 14:27  [ТС] 6
Вот. (Мне нужно точное значение)
0
Миниатюры
Найти количество простых чисел в заданном интервале   Найти количество простых чисел в заданном интервале  
SomniPhobia
352 / 256 / 101
Регистрация: 22.11.2017
Сообщений: 707
05.02.2019, 15:24 7
Лучший ответ Сообщение было отмечено wwmax как решение

Решение

wwmax, вот код. Для n = 50 000 время выполнения алгоритма половина 1 секунды.
Потестил программу на данных, что у тебя в таблице внизу первого скрина, где написано входное число и сколько должна выдать программа - всё верно выполняется.
C++
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
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <numeric>
#include <fstream>
 
using namespace std;
 
int main()
{
    //system("color 0A");
    //wcout.imbue(locale("rus_rus.866"));
    
    size_t nn;
 
    /*
    wcout << L"Введите значение n ";
    cin >> nn;
    */
 
    ifstream fin;
    fin.open("INPUT.TXT");
    fin >> nn;
    fin.close();
 
    size_t n = 2u * nn;
    auto start = clock();
    vector<bool> v(n + 1u, true);
    v[0u] = false;
    v[1u] = false;
    for (size_t p = 2u; p <= n;)
    {
        for (size_t d = p * p; d <= n; d += p)
        {
            v[d] = false;
        }
        auto it = find(v.begin() + p + 1u, v.end(), true);
        p = it - v.begin();
    }
    auto finish = clock();
    size_t count = accumulate(v.begin() + nn + 1, v.end() - 1, 0u);
 
    //wcout << L"Количество простых чисел от " << nn << L" (включительно) до " << n << L" (включительно) " << count << endl;
    
    
    ofstream fout;
    fout.open("OUTPUT.TXT");
    fout << count;
    fout.close();
    
 
    //wcout << L"На работу алгоритма потрачено секунд "
        //<< static_cast<double>(finish - start) / CLOCKS_PER_SEC << endl;
 
    /*
    //Вывод простых чисел на консоль
    size_t num = 0u;
    for (const auto &flag : v)
    {
        if (flag)
        {
            cout << num << " ";
        }
        ++num;
    }
    cout << endl;
    */
    
    //system("pause");
    return 0;
}
0
Миниатюры
Найти количество простых чисел в заданном интервале  
wwmax
0 / 0 / 0
Регистрация: 25.10.2018
Сообщений: 271
05.02.2019, 18:27  [ТС] 8
Спасибо большое) А легче это как-то можно сделать? Я ещё пока не всё понимаю.
0
SerVal
28 / 27 / 9
Регистрация: 16.04.2015
Сообщений: 262
05.02.2019, 23:07 9
SomniPhobia, что-то у Вас как-то медленно.

// функция проверяет простое ли число
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void isPrime(uint32_t candidate, bool *bResult)
{
    if (candidate == 2)   { *bResult = true; return; }
    if (!(candidate & 1)) { *bResult = false; return; }
 
    for (uint32_t i = 3; true; i += 2)
    {
        uint32_t q = candidate / i;
        if (q < i)  {
            *bResult = true; return;
        }
 
        if (candidate == q * i)  { *bResult = false; return; }
    }
 
    *bResult = true;
}

// функция ищет все простые числа в диапазоне lower_bound ... upper_bound.
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getAllPrimesInRange(uint32_t lower_bound, uint32_t upper_bound, std::vector<uint32_t> *output)
{
    uint32_t start_num, end_num = upper_bound;
 
    if (lower_bound & 1) start_num = lower_bound;
    else start_num = lower_bound + 1;
 
    std::vector<uint32_t> myPrimes;
    if (lower_bound == 2) myPrimes.push_back(2);
 
    bool bResult;
    for (uint32_t i = start_num; i <= end_num; i += 2U)
    {
        isPrime(i, &bResult);
        if (bResult)
            myPrimes.push_back(i);
    }
 
    *output = myPrimes;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "russian");  std::cout << endl;
 
    printCPUName();
 
    uint32_t lower_bound = 2;
    uint32_t upper_bound = 1000000U;
    std::vector<uint32_t>  output;
 
    std::cout << " Поиск простых чисел в диапазоне от " << lower_bound << " до " << upper_bound << std::endl;
    double total_time = (double)clock() / CLOCKS_PER_SEC;
    getAllPrimesInRange(lower_bound, upper_bound, &output);
 
    uint32_t n_primes = output.size();
 
    std::cout << " Найдено : " << n_primes << std::endl;
    std::cout << " Самое маленькое : " << output[0] << std::endl;
    std::cout << " Самое большое   : " << output.back() << std::endl;
    std::cout << " Время поиска    : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl;
 
    return 0;
}
*****
Результат:
C++
1
2
3
4
5
6
7
 Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz
 
 Поиск простых чисел в диапазоне от 2 до 1000000
 Найдено : 78498
 Самое маленькое : 2
 Самое большое   : 999983
 Время поиска    : 0.117 sec.
0
valen10
Параллельный Кот
1264 / 532 / 211
Регистрация: 25.03.2016
Сообщений: 1,186
Завершенные тесты: 1
06.02.2019, 05:01 10
SerVal, есть ли смысл сравнивать время работы двух разных алгоритмов на разном оборудовании, еще и измеренное в попугаях? Если выполнить измерения на одном компьютере, ваш вариант окажется медленнее, чем предложенный SomniPhobia.
0
06.02.2019, 05:01
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2019, 05:01

Подсчитать количество простых чисел в произвольном интервале
Подсчитать количество простых чисел в произвольном интервале. Границы интервала задаются с...

Вывести количество зеркально простых чисел на заданном участке
Задача:вывести количество зеркально простых чисел на заданном участке. Проблема:если я введу числа...

Определить количество введенных чисел значения которых находятся в заданном интервале
С клавиатуры вводятся действительные числа.Признак конца ввода-0. Определить количество чисел...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.