Алгоритмы

Об одном алгоритме поиска простых чисел

10 January

Как-то, ради интереса, я решил поискать в Сети материалы о нахождении всех простых чисел в диапазоне от 1 до N за линейное время. Нашлись некоторые статьи на английском, но описанные алгоритмы были несколько сложны для реализации. К сожалению, поиски на русском не увенчались успехом – были какие-то оптимизации, пытающиеся уменьшить объем памяти, константу в оценке времени, но ничего за O(N), так что я решил восполнить данный пробел.

Определение проблемы

Для начала, вспомним, что существует так называемое решето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
	int primesCount = 0;
	int sqrt_n = (int)sqrt((double)n);
	for (int i = 2; i < = n; ++i) {
		if (!notPrime[i]) {
			primes[primesCount++] = i;
			if (i <= sqrt_n) {
				for (int j = i * i; j <= n; j += i) {
					notPrime[j] = true;
				}
			}
		}
	}
	return primesCount;
}

Почему решето работает не за линейное время? Потому что одно число в нем может вычеркиваться несколько раз (во внутреннем цикле) . Если добиться, чтобы каждое число вычеркивалось не более одного раза, то, очевидно, алгоритм будет линейным.

Далее – описание линейного алгоритма

(a * b) % c

20 January

Опубликовал arti в Алгоритмы

Нет комментариев

На сайте TopCoder появилась очередная статья из раздела Feature Article – Primality Testing : Non-deterministic Algorithms, в начале которой описан любопытный метод вычисления произведения a * b % c, если все числа 64-битные и длинная арифметика не используется. Метод похож на быстрое возведение в степень и работает за O(log b).

Вот, собственно, код, немного оптимизированный мною:

long long multiply(long long a, long long b, long long c) {
   long long x = 0, y = a % c;
   b %= c;
   while (b > 0) {
       if (b & 1) {
           x += y;
           if (x >= c) x -= c;
       }
       y <<= 1;
       if (y >= c) y -= c;
       b >>= 1;
   }
   return x;
}