PMG
http://forum.pmg.org.ru/

Простые числа (primes)
http://forum.pmg.org.ru/viewtopic.php?f=3&t=1399
Страница 1 из 1

Автор:  MagicWolf [ 31 янв 2007 10:32 ]
Заголовок сообщения:  Простые числа (primes)

Нужен простой исходник для генерации простых чисел в пределах unsigned long. Хранить в таблице - много памяти. Функции вида:

Код:
int is_prime(unsigned long n)
{
    unsigned long i, n_sqrt;

    if ( n<=3 )
      return 1;
    if ( (n%2)==0 )
      return 0;

    n_sqrt = (unsigned long)sqrt((double)n);
    n_sqrt++;
    for (i = 3; i <= n_sqrt; i += 2)
       if (n % i == 0)
         return 0;

    return 1;
}


Довольно просто и работает медленно. Может кто, что видел?

Автор:  VicTeam [ 31 янв 2007 13:46 ]
Заголовок сообщения: 

Не исходник, но все же...

http://mathworld.wolfram.com/Rabin-Mill ... eTest.html

Автор:  VicTeam [ 31 янв 2007 14:35 ]
Заголовок сообщения: 

А вот с исходниками, но под GNU C и требуется его б-ка GMP,
где нужна ф-я mpz_probab_prime_p, но, наверное, ее текст можно найти
или самому написать.

http://www.trnicely.net/

Автор:  VicTeam [ 31 янв 2007 14:51 ]
Заголовок сообщения: 

А вот и функция:

http://macssh.cvs.sourceforge.net/macss ... iew=markup

Автор:  MagicWolf [ 31 янв 2007 14:59 ]
Заголовок сообщения: 

VicTeam писал(а):
Не исходник, но все же...

http://mathworld.wolfram.com/Rabin-Mill ... eTest.html


Не мне нужен исходник, желательно понятный, а то можно всю жизнь блуждать в этих формулах. Это помниться я в одной книге читал, что-то вроде этого: не пишите сами алгоритмы сжатия и шифрации, так как в них используются не тривиальные подходы, иначе на одних данных они будут работать, а на других нет. Вообще, такими алгоритмами люди всю жизнь занимаются.

Автор:  MagicWolf [ 31 янв 2007 15:05 ]
Заголовок сообщения: 

VicTeam писал(а):


Н-да, с этой функцией можно возиться всю жизнь ...

Автор:  MagicWolf [ 31 янв 2007 15:08 ]
Заголовок сообщения: 

В любом случае, большое спасибо! Этого я еще не видел ...

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/