Поиск простого числа

Germany.ru → Foren → Архив Досок→ Programmierung

Поиск простого числа

262 1 2 3 alle

Murr коренной житель08.11.06 18:22

NEW 08.11.06 18:22

in Antwort scorpi_ 08.11.06 17:55

Каким образом?
-----
За счет префиксного декремента, устанавливающего флаг равенства нулю. Правда для того, чтобы оценка (0.10) была верной там должен быть только развернутый код.
Вместо:
for( unsigned long counter = 1; counter < number; ++counter )
for( unsigned long counter = number; --counter; /* no */ )
И так же со вторым циклом.

#41

Murr коренной житель08.11.06 18:27

NEW 08.11.06 18:27

in Antwort scorpi_ 08.11.06 18:04

а твой алгоритм O(n^3)
------
он предлагал понизить до О(n*sqrt(n)), если я не ошибаюсь...

#42

scorpi_ скептик08.11.06 18:51

NEW 08.11.06 18:51

in Antwort Murr 08.11.06 18:22

Да, можно. Только измеримых результатов не даёт, так как это одна однотактовая команда.

#43

scorpi_ скептик08.11.06 19:40

08.11.06 19:40

in Antwort Murr 08.11.06 18:27, Zuletzt geändert 13.11.06 12:54 (scorpi_)

А, я его постинга сразу не заметил... Тогда да, О(n^1,5), первоначальный вариант кстати был конечно же О(n^2), а не в куб.
Короче вот -

В ответ на:

unsigned long get_prime_by_barmaglot( unsigned long number )
{
	if ( number == 1 )
		return 2;
	std::vector<unsigned long> found_primes( 1, 2 );
	found_primes.reserve( number );
	unsigned long i = 3;
	for( unsigned long counter = number - 1; counter; i += 2 )
	{
		for( unsigned long j = 0; j < found_primes.size(); ++j )
			if ( i < found_primes[j] * found_primes[j] ||  i % found_primes[j] == 0 )
				break;
		found_primes.push_back( i );
		--counter;
	}
	return i - 2;
}