Решето Эратосфена до 0xffffffff

@alexu_007 · Регистрация: 29.05.2015

Author24 — интернет-сервис помощи студентам

C++ (Qt)

    const quint32 N = 4294967280/2;
    const quint32 sqrt_N = sqrt(N)+1;
 
    QBitArray bbuf(N, false);
 
    quint32 i, j, k;
 
 
    for(i = 0; i < sqrt_N; i++)
    {
        if(!bbuf.at(i))
        {
            k = (i*2)+3;
            for(j = k*(i+1)+i; j < N; j+=k) bbuf[j] = true;
        }
    }

В общем всё работает, но при увеличении N хоть на единичку (до 4294967282/2) программа вылетает. После поисков ошибки выяснилось, что это предел QBitArraw по размеру:

C++ (Qt)

const quint32 N = 4294967280/2;
QBitArray bbuf(N, false);               // работает
 
const quint32 N = 4294967282/2;
QBitArray bbuf(N, false);               // вылетает

А если нужно дальше чем 0хFFFF FFFF, то что можно использовать вместо QBitArray?

@Wyn · 19.04.2016, 22:54

QByteArray? Он будет ровно в 8 раз больше. =)

Байт · 20.04.2016, 11:17

alexu_007, вообще-то решето Эратосфена очень хорошо укладывается тридцатками в байт
Вызвано это тем удивительным фактом, что все простые числа, большие 30, при делении на 30 дают один из 8-ми остатков: 1, 7, 11, 13, 17, 19, 23, 29

@icpu · 20.04.2016, 12:06

C++ (Qt)

1	const quint32 N = 4294967282ULL/2;

попробуйте

@alexu_007 · 20.04.2016, 14:21 **[ТС]**

Сообщение от Байт

вообще-то решето Эратосфена очень хорошо укладывается тридцатками в байт

Я знаю, и у меня даже реализация этого алгоритма есть. Но там много вычислений и он медленный.

Добавлено через 35 минут

Сообщение от icpu

попробуйте

Не работает.

@icpu · 20.04.2016, 15:43

А что я туплю, в Qt же размеры контейнеров int'овые. Короче, никак, только массив массивов.

@alexu_007 · 20.04.2016, 17:06 **[ТС]**

bitset ещё есть, как правильно объявить такой массив?

Байт · 20.04.2016, 18:09

Посмотрите здесь. Может быть найдете интересное...
Быстрая проверка натурального числа на простоту

@alexu_007 · 20.04.2016, 20:15 **[ТС]**

Да мне собсна не очень нужно, так, спортивный интерес.

К слову, решето эрастофена до максимума (последнее простое число 4 294 967 279) у меня строится за 37 сек. В 32-битное число влезает ещё одно простое 4 294 967 291, но размера QByteArray для него уже не хватает. Простой перебор делителей работает намного быстрее, вот такое число 10 000 000 000 000 061 нашлось за 0,8 сек, но есть разница - перебор делителей находит одно число, тогда как решето эрастофена всю последовательность от 2 до 4,29 млрд (всего 203 278 090 штук) и оставляет их в памяти.

Просто теоретически интересно, как быть, если нужна более длинная последовательность?

@kolts · 20.04.2016, 20:33

массив чаров откушает столько сколько есть памяти.

Байт · 20.04.2016, 20:46

Сообщение от alexu_007

теоретически интересно, как быть, если нужна более длинная последовательность?

Пиши в файл. Скорость резко упадет, но памяти в твоем распоряжении окажется значительно больше. Известная дилемма "Скорость - Память"
Кстати, упаковка решета тридцатками увеличивает максимальное число в 30/8 раз. Правда, его уже интом не представить, придется к длинной арифметике обращаться... Но если интересуют действительно большие числа, причем любые, а не специальные, типа чисел Мерсена, то без длинной арифметики все равно не обойтись...

Добавлено через 7 минут

Сообщение от kolts

массив чаров откушает столько сколько есть памяти.

Ой, не уверен я. Памяти может быть у много, не обязательно 2 Гб, как у Винда, а хоть 1000 Гб. Но char X[N]... - N - int.
Конечно, все зависит от разрядности, как компа, так и транслятора. Если Комп с трансляторам договорятся, что int = int64, то еще много времени пройдет, пока такая память появится, что int-а не хватит, чтобы ее обслужить

@kolts · 20.04.2016, 22:20

Я не понял ваш последний пост.
Вообще я думаю лучше хранить эти числа в массиве строк чаров. Чары же позволяют закодировать все что угодно. Маленькие числа будем кодировать 1 байтом, далее 2 байта и так далее.
В первом элементе массива у нас буду хранится 1 байтовые инты, во втором элементе 2 -х байтовые и так далее.
В первом элементе у нас до 256 и так далее. Таким образом будет экономиться память.

@nmcf · 20.04.2016, 23:30

Сообщение от alexu_007

bitset ещё есть, как правильно объявить такой массив?

C++

1	bitset<N> bbuf;

@alexu_007 · 21.04.2016, 06:41 **[ТС]**

В файл это несерьёзно... жизни не хватит. Массив char интереснее, но там нада как-то c битами работать - нужно подумать. До длинной арифметики ещё далеко, т.к. есть quint64 - быстродействия и на него не хватит.

Всем спасибо. А bitset сдулся всего на 16 млн., код "bitset<17000000> buff;" закончился ошибкой. QbitArraw круче, там 2 млрд. с хвостиком.

@nmcf · 21.04.2016, 10:22

Сообщение от alexu_007

А bitset сдулся всего на 16 млн.

Его нужно создавать динамически.

C++

1	std::bitset<N> *bs = new std::bitset<N>;

@kolts · 21.04.2016, 10:43

Так что в итоге надо получить? Если массив бит то:
char a[1000000];
char[0] = 0b00110101 2,3,5,7 Это 0х35 символ '5'
char[1] = 0b00010100 11,13 Это 0х14 символ DC4
и т.д.
Берете порцию из восьми чисел и записываете их в соответствующий элемент. Было предложено 30 чисел в 1 байт, но долго вроде будет, а вы не делите, помещайте 8 чисел.
А вообще можно в два потока считать для скорости. Один пусть считает до определенного числа а другой больше

Байт · 21.04.2016, 10:56

Сообщение от kolts

Было предложено 30 чисел в 1 байт, но долго будет

Позвольте выразить сомнения... Потенциально тут уже содержится сокращение времени, так как проверять надо меньше чисел и на меньшее количество надо делить... Так что все зависит от вашего алгоритма и радиуса кривизны рук. А вынимать простые (и потенциально простые) числа из упаковки "30 в 8", ну это в самом деле просто и совершенно незатратно по времени.

@kolts · 21.04.2016, 11:00

Вы пропустили слово вроде, так сказал автор, я не проверял. По памяти намного лучше. Надо еще в несколько потоков для скорости

@alexu_007 · 21.04.2016, 20:27 **[ТС]**

Сообщение от nmcf

Его нужно создавать динамически.

C++ (Qt)

    const quint32 N = 1000000/2;
 
    bitset<N> *bs = new bitset<N>;
    bs[2] = true;
 
    return;

Программа компилируется, запускается - и сразу вылетает с ошибкой: Erastofen.exe завершился с кодом -1073741819. Что я делаю не так?

@icpu · 21.04.2016, 20:42

try{ bitset<N> *bs = new bitset<N>; bs[2] = true; } catch (std::exception& e) { qDebug() << e.what(); }

@Wyn 1070 / 652 / 229 Регистрация: 14.01.2016 Сообщений: 2,031 Записей в блоге: 9
	19.04.2016, 22:54	2
	QByteArray? Он будет ровно в 8 раз больше. =) 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	20.04.2016, 11:17	3
	alexu_007, вообще-то решето Эратосфена очень хорошо укладывается тридцатками в байт Вызвано это тем удивительным фактом, что все простые числа, большие 30, при делении на 30 дают один из 8-ми остатков: 1, 7, 11, 13, 17, 19, 23, 29 0

@alexu_007 661 / 662 / 106 Регистрация: 29.05.2015 Сообщений: 3,967
	20.04.2016, 14:21 [ТС]	5
	Сообщение от Байт вообще-то решето Эратосфена очень хорошо укладывается тридцатками в байт Я знаю, и у меня даже реализация этого алгоритма есть. Но там много вычислений и он медленный. Добавлено через 35 минут Сообщение от icpu попробуйте Не работает. 0

@icpu 487 / 365 / 93 Регистрация: 10.03.2011 Сообщений: 1,513 Записей в блоге: 5
	20.04.2016, 15:43	6
	А что я туплю, в Qt же размеры контейнеров int'овые. Короче, никак, только массив массивов. 0

@alexu_007 661 / 662 / 106 Регистрация: 29.05.2015 Сообщений: 3,967
	20.04.2016, 17:06 [ТС]	7
	bitset ещё есть, как правильно объявить такой массив? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	20.04.2016, 18:09	8
	Посмотрите здесь. Может быть найдете интересное... Быстрая проверка натурального числа на простоту 0

@alexu_007 661 / 662 / 106 Регистрация: 29.05.2015 Сообщений: 3,967
	20.04.2016, 20:15 [ТС]	9
	Да мне собсна не очень нужно, так, спортивный интерес. К слову, решето эрастофена до максимума (последнее простое число 4 294 967 279) у меня строится за 37 сек. В 32-битное число влезает ещё одно простое 4 294 967 291, но размера QByteArray для него уже не хватает. Простой перебор делителей работает намного быстрее, вот такое число 10 000 000 000 000 061 нашлось за 0,8 сек, но есть разница - перебор делителей находит одно число, тогда как решето эрастофена всю последовательность от 2 до 4,29 млрд (всего 203 278 090 штук) и оставляет их в памяти. Просто теоретически интересно, как быть, если нужна более длинная последовательность? 0

@kolts 44 / 44 / 12 Регистрация: 05.04.2015 Сообщений: 345
	20.04.2016, 20:33	10
	массив чаров откушает столько сколько есть памяти. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	20.04.2016, 20:46	11
	Сообщение от alexu_007 теоретически интересно, как быть, если нужна более длинная последовательность? Пиши в файл. Скорость резко упадет, но памяти в твоем распоряжении окажется значительно больше. Известная дилемма "Скорость - Память" Кстати, упаковка решета тридцатками увеличивает максимальное число в 30/8 раз. Правда, его уже интом не представить, придется к длинной арифметике обращаться... Но если интересуют действительно большие числа, причем любые, а не специальные, типа чисел Мерсена, то без длинной арифметики все равно не обойтись... Добавлено через 7 минут Сообщение от kolts массив чаров откушает столько сколько есть памяти. Ой, не уверен я. Памяти может быть у много, не обязательно 2 Гб, как у Винда, а хоть 1000 Гб. Но char X[N]... - N - int. Конечно, все зависит от разрядности, как компа, так и транслятора. Если Комп с трансляторам договорятся, что int = int64, то еще много времени пройдет, пока такая память появится, что int-а не хватит, чтобы ее обслужить 0

@kolts 44 / 44 / 12 Регистрация: 05.04.2015 Сообщений: 345
	20.04.2016, 22:20	12
	Я не понял ваш последний пост. Вообще я думаю лучше хранить эти числа в массиве строк чаров. Чары же позволяют закодировать все что угодно. Маленькие числа будем кодировать 1 байтом, далее 2 байта и так далее. В первом элементе массива у нас буду хранится 1 байтовые инты, во втором элементе 2 -х байтовые и так далее. В первом элементе у нас до 256 и так далее. Таким образом будет экономиться память. 0

@alexu_007 661 / 662 / 106 Регистрация: 29.05.2015 Сообщений: 3,967
	21.04.2016, 06:41 [ТС]	14
	В файл это несерьёзно... жизни не хватит. Массив char интереснее, но там нада как-то c битами работать - нужно подумать. До длинной арифметики ещё далеко, т.к. есть quint64 - быстродействия и на него не хватит. Всем спасибо. А bitset сдулся всего на 16 млн., код "bitset<17000000> buff;" закончился ошибкой. QbitArraw круче, там 2 млрд. с хвостиком. 0

@kolts 44 / 44 / 12 Регистрация: 05.04.2015 Сообщений: 345
	21.04.2016, 10:43	16
	Так что в итоге надо получить? Если массив бит то: char a[1000000]; char[0] = 0b00110101 2,3,5,7 Это 0х35 символ '5' char[1] = 0b00010100 11,13 Это 0х14 символ DC4 и т.д. Берете порцию из восьми чисел и записываете их в соответствующий элемент. Было предложено 30 чисел в 1 байт, но долго вроде будет, а вы не делите, помещайте 8 чисел. А вообще можно в два потока считать для скорости. Один пусть считает до определенного числа а другой больше 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	21.04.2016, 10:56	17
	Сообщение от kolts Было предложено 30 чисел в 1 байт, но долго будет Позвольте выразить сомнения... Потенциально тут уже содержится сокращение времени, так как проверять надо меньше чисел и на меньшее количество надо делить... Так что все зависит от вашего алгоритма и радиуса кривизны рук. А вынимать простые (и потенциально простые) числа из упаковки "30 в 8", ну это в самом деле просто и совершенно незатратно по времени. 0

@kolts 44 / 44 / 12 Регистрация: 05.04.2015 Сообщений: 345
	21.04.2016, 11:00	18
	Вы пропустили слово вроде, так сказал автор, я не проверял. По памяти намного лучше. Надо еще в несколько потоков для скорости 0

@icpu 487 / 365 / 93 Регистрация: 10.03.2011 Сообщений: 1,513 Записей в блоге: 5
	21.04.2016, 20:42	20
	try{ bitset<N> *bs = new bitset<N>; bs[2] = true; } catch (std::exception& e) { qDebug() << e.what(); } 0