|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 20 Mar 2002 17:00:38
To : Mike Gorchak
Subject : Re: Пpостые числа...
--------------------------------------------------------------------------------
Mike Gorchak wrote:
> > У кого нить есть алгоpитм поиска пpостых чисел на отpезке от 1 до N...
> Самый тупой и быстрый способ (из тупых), массив 63Mb - это для хранения
> простых чисел, можно урезать до того, который тебе нужен. Цикл до
> 0xFFFFFFFFUL замени до N.
> P.S. Мне в проге надо было получить все 32bit простые числа для анализа.
> for (i=3; i<MAX_N; i+=2)
> {
> for (unsigned long p=0; p<primecount; p++)
> if (i%primes[p]==0)
> break;
> if (p==primecount)
> {
> primes[primecount]=i;
> primecount++;
> printf("%d\n", i);
> }
> }
Dear Mike, Вы скажите лучше , сколько суток работает это?
И чисел не 63Mб, и даже не 63M*sizeof(long) а немного больше 400Mб, если хранить
именно так, как у Вас.
Файл хранить лучше в виде одно нечётное число - один бит.
Можно даже компактнее, почти вдвое, если заметить, что из каждых 30 чисел
кандидатов в простые только 8
Это 30*K+{1,07,11,13,17,19,23,29}. Прочие делятся на 2,3,5. Однако программулка
сильно прибавляет в размере, и ещё сильнее теряет в скорости. Сейчас вполне
можно позволить себе под каждое нечётное от 0 до 2^32 выделить бит памяти -
всего 256М.
Для поиска всех простых чисел от 0 до 2^31 совершенно тупое решето Эратосфена за
6 минут выдаёт результат. Это без записи файла на диск.
Если нужна программа - пишите, поищем.
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
