Вход на сайт
Поиск простого числа
262 просмотров
Перейти к просмотру всей ветки
scorpi_ скептик
в ответ Murr 08.11.06 18:27, Последний раз изменено 13.11.06 12:54 (scorpi_)
А, я его постинга сразу не заметил... Тогда да, О(n^1,5), первоначальный вариант кстати был конечно же О(n^2), а не в куб.
Короче вот -
Даёт ответ за 15сек, против 0.85 для решета (number =1000000)
Короче вот -
В ответ на:
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;
}
Даёт ответ за 15сек, против 0.85 для решета (number =1000000)