Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
1

Решето Эратосфена (сегмент): медленно работает - как можно ускорить?

19.01.2017, 16:59. Показов 582. Ответов 4
Метки нет (Все метки)

Подсчёт числа простых чисел в диапазоне от "from" до "to"
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
typedef UINT64 Number;
 
__device__ Number eratosthenesSingleBlock(const Number from, const Number to)
{
    const Number memorySize = (to - from + 1) / 2;
 
    // initialize
    char* isPrime = new char[memorySize];
    memset(isPrime, 1, memorySize);
 
    for (Number i = 3; i*i <= to; i += 2)
    {
        // skip multiples of three: 9, 15, 21, 27, ...
        if (i >= 3 * 3 && i % 3 == 0)
            continue;
        // skip multiples of five
        if (i >= 5 * 5 && i % 5 == 0)
            continue;
        // skip multiples of seven
        if (i >= 7 * 7 && i % 7 == 0)
            continue;
        // skip multiples of eleven
        if (i >= 11 * 11 && i % 11 == 0)
            continue;
        // skip multiples of thirteen
        if (i >= 13 * 13 && i % 13 == 0)
            continue;
 
        // skip numbers before current slice
        Number minJ = ((from + i - 1) / i)*i;
        if (minJ < i*i)
            minJ = i*i;
 
        // start value must be odd
        if ((minJ & 1) == 0)
            minJ += i;
 
        // find all odd non-primes
        for (Number j = minJ; j <= to; j += 2 * i)
        {
            Number index = j - from;
            isPrime[index / 2] = 0;
        }
    }
 
    // count primes in this block
    UINT32 found = 0;
    for (UINT32 i = 0; i < memorySize; i++)
        found += isPrime[i];
    // 2 is not odd => include on demand
    if (from <= 2)
        found++;
 
    delete[] isPrime;
    return found;
}
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.01.2017, 16:59
Ответы с готовыми решениями:

Решето Эратосфена. Как ускорить?
Этот код не проходит задачу. доля секунды. как ускорить. или каким методом проидет #include...

Прокомментируйте оставшиеся строчки, не понимаю как работает "Решето Эратосфена"
#include &lt;iostream&gt; //подключение стандартной библиотеки ввода-вывода using namespace std;...

Как разложить число на простые множители, используя решето Эратосфена?
Я только код для решета Эратосфена знаю(

Решето Эратосфена
Кому надо - программа &quot;Решето Эратосфена&quot; на C++. Записывает в файл 1 000 000 первых простых чисел...

4
Форумчанин
Эксперт CЭксперт С++
8169 / 5017 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
19.01.2017, 17:02 2
http://e-maxx.ru/algo/eratosthenes_sieve
Решето Эратосфена
Самый быстрый алгоритм Евклида вычисления НОД
0
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
19.01.2017, 17:14  [ТС] 3
Спасибо, это я уже смотрел. Нахождения простых чисел в диапазоне от Num1 до Num2 там нетути.
Все ищут от "печки" - с нуля или двойки.
0
Dimension
584 / 452 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
19.01.2017, 19:16 4
SerVal, потому что решето по другому не будет работать ,вот вообще линейное решето http://e-maxx.ru/algo/prime_sieve_linear
думаю потом по массиву от нум1 до нум2 сами сможете пробежать
0
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
19.01.2017, 19:35  [ТС] 5
Цитата Сообщение от Dimension Посмотреть сообщение
потому что решето по другому не будет работать
Решето Эратосфена, приведённое в первом посте вполне себе работает.
*хотелось бы чтобы работало маленько побыстрее.
C++
1
2
3
4
5
6
7
8
9
10
11
D:\aProjects\CudaTest\x64\Release>PrimeSearchCuda.exe
 
Prime search:   4000000000000 .. 4001000000000
 
Accelerator: GeForce GTX 460
Found : 34462887
First prime :   4000000000039
Last prime  :   4000999999987
=============
Exec time : 110 seconds.
Primes/sec : 313663
Большой диапазон разбивается на много маленьких блоков (по 8 килобайт).
И для каждого блока решетом подсчитывается число простых. Потом суммируется для всех блоков.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.01.2017, 19:35

Решето Эратосфена
Как можно реализовать? Подскажите плиз

Решето Эратосфена
Простое число — это любое целое число, которое точно делится без остатка только само на себя и на...

Решето Эратосфена
В общем задание посчитать количество простых чисел до заданного числа N. Написал такой алгоритм,...

Решето Эратосфена
Здравствуйте. Реализовал алгоритм &quot;Решето Эратосфена&quot; в виде класса. Взгляните, пожалуйста, и...


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

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

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