Primality test algorithm

[Tempura]

Какой является самым популярным если можно так выразиться по своей несложности.
Собственно вопрос

[SVK]

Хм...

Конечно: "Напечатать 'Hello, World!'"

[vaduz]

http://en.wikipedia.org/wiki/Primality_test

Мне лично во многих случаях хватало либо битовой строчки, либо таблицы.

[Tempura]

википидию я видела. Спасибо. Там нескольно алгоритмов. Меня инересует наиболее простой из них:-)

А про какую вы таблицу говорите? а если число 30 значное?

[vaduz]

А про какую вы таблицу говорите? а если число 30 значное?

Ну вы бы сперва область интересов описали.
Нафига вам лично это нужно?

[venco]

Самый простой не обязательно подойдёт вам.
Чтобы выбрать, надо знать какой диапазон чисел, насколько надёжно надо знать что число простое, и т.д.

Как вариант простого решения - воспользоваться готовой библиотекой:

Code: Select all

  if ( new java.math.BigInteger("12345678901").isProbablePrime(32) )
    System.out.println("prime, probably");

[PavelM]

Какой является самым популярным если можно так выразиться по своей несложности.
Собственно вопрос

Rabin-Miller test

но лучше послушайте venco и возьмите что-то готовое

[OtecFedor]

Вопрос на interview "can you prove that if P is a prime number P^2-1 will divide by 24 without a residue?" Я понимаю if p is prime than it can be peresnted as 2n+-1 and 3n+-1 и наверное можно показать что P^2-1 делится на 24. Кто-то знает вывод?

[venco]

Вопрос на interview "can you prove that if P is a prime number P^2-1 will divide by 24 without a residue?" Я понимаю if p is prime than it can be peresnted as 2n+-1 and 3n+-1 и наверное можно показать что P^2-1 делится на 24. Кто-то знает вывод?

Это неверно для P=2,3.
А для P>3 вы уже почти доказали, там всё просто.

[mikeG]

Вопрос на interview "can you prove that if P is a prime number P^2-1 will divide by 24 without a residue?" Я понимаю if p is prime than it can be peresnted as 2n+-1 and 3n+-1 и наверное можно показать что P^2-1 делится на 24. Кто-то знает вывод?

Это верно не для всех простых чисел, а для всех, кроме 2 и 3.

P^2 - 1 = (P-1)(P+1).
Одно из них делится на два, другое - на четыре. И одно из них делится на три => произведение делится на 24.

[OtecFedor]

P^2 - 1 = (P-1)(P+1).
Одно из них делится на два, другое - на четыре. И одно из них делится на три => произведение делится на 24.

Спасибо, при таком разложении деиствительно просто и очевидно, у меня в условиях стесса как-то слишком запутано получилось.