|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 21 Mar 2002 07:07:25
To : Andrew Doroshev
Subject : Re: Пpостые числа...
--------------------------------------------------------------------------------
Привет! "Andrew Doroshev" <netlog@altavista.net> сообщил(а):
AD> Файл хранить лучше в виде одно нечётное число - один бит.
AD> Можно даже компактнее, почти вдвое, если заметить, что из каждых 30
AD> чисел кандидатов в простые только 8
AD> Это 30*K+{1,07,11,13,17,19,23,29}.
Все равно 137 Mb получается. Далеко не во всякий компьютер влезет.
Hо для поиска простых чисел в диапазоне [2..N] достаточно прореживать решето
по простым числам до sqrt(N) включительно. Следовательно для поиска простых
чисел от 0 до (2^32)-1 можно использовать "блочный" алгоритм: сначала ищем
(тем же решетом) просты числа в диапазоне [0..(2^16)-1], а потом достраиваем
решето блоками по 2^16 чисел. При этом программа спокойно влезает в
DOS'овские 640 Kb:
#include <stdio.h>
typedef struct{
long Pos;
long Val;
} _Tab_Val;
_Tab_Val Tab_Val[0x8000l];
int Cnt_Val = 0;
class{
private:
char Buf_Bit[0x1000];
void Set(long Num_Bit){
this->Buf_Bit[Num_Bit>>3]|=(1<<(Num_Bit&7));
}
public:
int Tst(long Num_Bit){
return (this->Buf_Bit[Num_Bit>>3]&(1<<(Num_Bit&7)))==0;
}
void Gen(_Tab_Val &Tmp){
long i;
for(i=Tmp.Pos; i<0x8000u; i+=Tmp.Val)this->Set(i);
Tmp.Pos=i-0x8000l;
}
void Clr(void){
for(int i=0; i<0x1000; this->Buf_Bit[i++]=0);
}
} Tab_Bit;
void Gen_Val(void){
for(long i=1; i<0x8000l; i++){
if(Tab_Bit.Tst(i)){
Tab_Val[Cnt_Val].Pos=i;
printf("%lu\n", (Tab_Val[Cnt_Val].Val=(i<<1)+1));
Tab_Bit.Gen(Tab_Val[Cnt_Val++]);
}
}
}
int main(void){
printf("2\n");
Gen_Val();
for(unsigned long i=0x8000l; i<0x80000000l; i+=0x8000l){
long j;
Tab_Bit.Clr();
for(j=0; j<Cnt_Val; j++){
Tab_Bit.Gen(Tab_Val[j]);
}
for(j=0; j<0x8000l; j++){
if(Tab_Bit.Tst(j)){
printf("%lu\n", ((i+j)<<1)+1);
}
}
}
}
Кажется, работает...
С уважением, Андрей.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
