Как обнаружить простое число

Question

Я знаю, что есть много бинарных операций, чтобы показать, что что-то верно например, мы можем показать, является ли число степенью двойки или что-то еще, есть ли какая-то теория или специальный двоичный метод, чтобы показать, является ли число простым?

Answer 1

Определить, является ли число простым, не очень просто!

Прочтите эту статью о PRIMES в прорыве P : http://www.ams.org/notices/200305/fea-bornemann.pdf, чтобы дать вам представление о том, насколько серьезной является эта проблема.

Эта новостная статья может быть легче читать: http://members.cox.net/mathmistakes/primes.htm

Короче говоря, если вы найдете простой «двоичный метод», вы станете знаменитым!

Answer 2

Как правило, вы просто чек .

Answer 3

Хороший пример алгоритма Sieve для поиска простых чисел можно найти на нашей странице этой википедии.

Сито Эратосфена

Один из наиболее интересных методов поиска простых чисел, и сито Эйлера (затронутое внизу той же страницы) немного ускоряет его.

Answer 4

bool isPrime(int number){

    if(number < 2) return false;
    if(number == 2) return true;
    if(number % 2 == 0) return false;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return false;
    }
    return true;

}

Примечание. Это будет медленно, если ваш ввод больше 10 ^ 9.

Answer 5

Существует действительно большая разница между степенной силой 2 и простыми числами.
Если вы посмотрите на нашу систему представления чисел: 1243 = 1 * 10 ³ + 2 * 10 ² + 4 * 10 ¹ + 3 * 10 ⁰
Довольно легко определить, когда число можно разделить на 10 (младшая цифра равна нулю) или является степенью 10 (все младшие цифры равны нулю и имеют значение «1», или сумма всех цифр равна 1).
То же самое для двоичного кода: 1243 = 1 * 2 ¹⁰ + 0 * 2 ⁹ + 0 * 2 ⁸ + 1 * 2 ⁷ + 1 * 2 ⁶ + 0 * 2 ⁵ + 1 * 2 ⁴ + 1 * 2 ³ + 0 * 2 ² + 1 * 2 ¹ + 1 * 2 ⁰
Вы можете проверить цифры, чтобы проверить, можно ли разделить число на 2 или даже на степень 2 таким же образом, как для представления числа на основе 10.

Теперь рассмотрим другие системы представления чисел. Я предполагаю, что римские цифры должны иметь некоторые интересные свойства, но вы, вероятно, интересуетесь чем-то вроде: 1243 = 2 ⁰ * 3 ⁰ * 5 ⁰ * 7 ⁰ * 11 ¹ * 13 ⁰ * 17 ⁰ * 19 ⁰ * 23 ⁰ * 29 ⁰ * 31 ⁰ * 37 ⁰ * 41 ⁰ * 43 ⁰ * 47 ⁰ * 53 ⁰ * 59 ⁰ * 61 ⁰ * 67 ⁰ * 71 ⁰ * 73 ⁰ * 79 ⁰ * 83 ⁰ * 89 ⁰ * 97 ⁰ * 101 ⁰ * 103 ⁰ * 107 ⁰ * 109 ⁰ * 113 ¹ = 11 ¹ * 113 ¹ = [0,0,0,0,1 , 0,0,0,0,0 ...] _{простой основе}
То есть число кодируется как произведение степеней простых чисел. Такая система обладает хорошим свойством выполнять различные проверки, связанные с простыми числами, гораздо проще, чем в битах или в десятичных числах.

P.S. В то время как системы с взвешенной суммой дают вам простой способ подсчета сумм и разностей, системы с мощным продуктом упрощают умножение и деление.