Описание тега primality-test
Тест на простоту - это алгоритм определения того, является ли входное число простым.
2
ответа
Тест на примитивность MillerRabin в C#
Добро пожаловать. Я пытаюсь реализовать тест MillerRabin для проверки, является ли большое заданное число простым числом. Вот мой код: public static bool MillerRabinTest(BigInteger number) { BigInteger d; var n = number - 1; var s = FindK(n, out d);…
24 ноя '15 в 14:05
2
ответа
Тест на простоту чисел вида 10^n + k
У меня есть некоторые числа в форме 10N + K, где N составляет около 1000, а K действительно мало (ниже 500). Я хочу проверить эти числа на простоту. В настоящее время я использую тест Ферма по базе 2, перед которым проверяются небольшие факторы (<10…
14 окт '11 в 16:22
0
ответов
Проблемы с тестом Миллера-Рабина
Я пытаюсь отладить мою реализацию стандартного (то есть вероятностного) теста Миллера-Рабина. Это код прямо сейчас, с элементарным выполнением теста в main метод: #include <iostream> #include <random> typedef unsigned long long int ulli;…
13 окт '17 в 15:39
32
ответа
Проверьте, является ли число простым числом
Я просто хотел бы спросить, является ли это правильным способом проверки, является ли число простым или нет? потому что я прочитал, что 0 и 1 не являются простым числом. int num1; Console.WriteLine("Accept number:"); num1 = Convert.ToInt32(Console.R…
01 апр '13 в 12:07
5
ответов
Программа, которая проверяет, является ли число простым числом
Здравствуйте, я создал эту программу, чтобы проверить, является ли число простым числом. Это работает, но почему-то говорит, что 999 - простое число. Где моя ошибка Было бы здорово, если бы кто-то объяснил. Благодарю вас! Вот моя программа: number =…
24 окт '16 в 03:41
2
ответа
Есть ли серьезная неэффективность в этом псевдокоде Миллера-Рабина в CLRS?
Этот вопрос может на самом деле не иметь ничего общего с процедурой проверки первичности Миллера-Рабина; это может только легкий анализ некоторого простого псевдокода. На стр. 969 CLRS (Введение в алгоритмы 3ed) представлена вспомогательная функци…
23 янв '18 в 13:53
1
ответ
Как спроектировать машину Тьюринга, которая проверяет, является ли число простым или нет?
Я мог только понять, что логика должна была включать логику умножения и деления на машинах Тьюринга. Но на самом деле я не могу разобрать точное решение.
03 дек '18 в 15:17
1
ответ
Почему один из этих генераторов простых чисел быстрее другого?
В последнее время интересуются простыми тестами на простоту. У меня есть следующие две функции, которые возвращают список всех простых чисел до заданного ввода. Первое, что я сделал, другое основано на псевдокоде Википедии для тестов на простоту. За…
22 янв '16 в 17:20
2
ответа
Простое число Логика, n/2 условие в цикле
Следующий код для простого числа. Я хочу знать, почему мы используем i<=n/2 состояние в цикле. Программа C: #include <stdio.h> int main() { int n, i, flag = 0; printf("Enter a positive integer: "); scanf("%d",&n); for(i=2; i<=n/2; ++…
26 окт '17 в 16:37
3
ответа
Какой самый быстрый алгоритм для идентификации простых чисел из массива случайных чисел?
У меня есть массив случайных чисел, и я должен вернуть простые числа из этого массива. Я знаком с решением root(n) (n - это конкретное число, а не размер массива). Я не могу применить сито Эратосфена, так как оно работает с числами в определенном ди…
12 янв '19 в 09:59
0
ответов
Объясните параграф Википедии о тестировании на первичность
В теории вычислительной сложности формальный язык, соответствующий простым числам, обозначается как PRIMES. Легко показать, что PRIMES находится в Co-NP: его дополнение COMPOSITES находится в NP, потому что можно решить сложность, недетерминистическ…
18 янв '19 в 21:28
2
ответа
Проверьте простое число, используя рекурсивную вспомогательную функцию
Я пытаюсь проверить, является ли число простым с использованием рекурсии. Мне нужно было использовать рекурсивную вспомогательную функцию, но я не уверен, как мне это реализовать. Я думаю, что знаю алгоритм, но я никогда не пытался использовать реку…
18 янв '19 в 16:55
3
ответа
Какие свидетели мне нужны для теста Рабина-Миллера на числа до 10¹⁸?
Какого набора свидетелей достаточно, чтобы критерий Миллера-Рабина был верным для всех чисел до 10¹⁸? Я знаю, что использование простых чисел до 17 в качестве свидетелей достаточно для n < 341550071728321.
05 мар '14 в 09:55
2
ответа
Детерминистская проверка, является ли большое число простым или составным?
Я ищу алгоритм проверки простоты больших (например, 10200) чисел. Есть ли хорошие алгоритмы? В идеале я бы предпочел алгоритм, который не является вероятностным. Примечание. Числа состоят из 50 и менее 200 цифр.
05 фев '12 в 19:56
3
ответа
Нечетная математическая ошибка в Java
Я пишу программу для демонстрации вероятностного тестирования Миллера-Рабина на Java. Код в значительной степени готов... import java.util.Random; import java.util.Scanner; /** * Program to demonstrate Miller-Rabin primality testing * * @author Nick…
30 мар '15 в 02:29
1
ответ
Консолидированная функция намного медленнее
Я написал функцию isPrime. Он проверяет, является ли данное число простым или нет. Последний "прайм" список дается отдельно. prime :: [Integer] prime = 2 : filter isPrime [3..] isPrime :: Integer -> Bool isPrime n | n < 2 = False isPrime n = a…
30 окт '17 в 10:12
2
ответа
Простая рекурсия - как это работает? (Python)
Мне было интересно, как эта программа знает, является ли число простым или нет. Я понимаю, что он проверяет остатки, чтобы найти четные числа для деления, но откуда он знает, что число имеет только 2 фактора? Я новичок в концепции рекурсии, поэтому …
05 ноя '16 в 13:33
3
ответа
Путать на Миллер-Рабин
В качестве упражнения для себя я применяю тест Миллера-Рабина. (Работает через SICP). Я понимаю маленькую теорему Ферма и смог успешно ее реализовать. В испытании Миллера-Рабина меня запутали, это бизнес "1 mod n". Разве 1 mod n (n - случайное цел…
17 сен '10 в 07:24
2
ответа
Хаскелл Прайм-тестирование путаницы
Так что я совершенно новичок в Хаскеле, надеюсь, это не так уж и много. В любом случае я пытался создать функцию, чтобы определить, является ли число простым. Основная идея заключается в следующем: если дано число, посмотрите, делится ли оно на любо…
13 июн '12 в 16:38
4
ответа
Первичность числа
Известно, что для проверки, является ли число n простым или нет, нам просто нужно проверить, имеет ли он коэффициент меньше квадратного корня из n. Мой вопрос не достаточно ли проверить все простые числа меньше, чем квадратный корень из n.
25 фев '17 в 10:44