Генерация ДЕЙСТВИТЕЛЬНО больших начал
Функциональный подход с ES2015
Вычисление difference между двумя массивами является одной из операций Set. Термин уже указывает, что для увеличения скорости поиска следует использовать собственный тип Set. В любом случае, при вычислении разницы между двумя наборами есть три перестановки:
[+left difference] [-intersection] [-right difference]
[-left difference] [-intersection] [+right difference]
[+left difference] [-intersection] [+right difference]
Вот функциональное решение, которое отражает эти перестановки.
Слева difference:
// small, reusable auxiliary functions
const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// left difference
const differencel = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? false
: true
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run the computation
console.log( differencel(xs) (ys) ); Справа difference:
differencer является тривиальный. Это просто differencel с перевернутыми аргументами. Для удобства вы можете написать функцию: const differencer = flip(differencel). Вот и все!
Симметричный difference:
Теперь, когда у нас есть левый и правый, реализация симметричного difference также становится тривиальной:
// small, reusable auxiliary functions
const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const concat = y => xs => xs.concat(y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// left difference
const differencel = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? false
: true
) (xs);
};
// symmetric difference
const difference = ys => xs =>
concat(differencel(xs) (ys)) (flip(differencel) (xs) (ys));
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run the computation
console.log( difference(xs) (ys) );Думаю, этот пример является хорошей отправной точкой для получения впечатления о том, что означает функциональное программирование:
Программирование с использованием строительных блоков, которые могут быть соединены вместе разными способами.
5 ответов
Вы не можете точно генерировать простые числа. Вы случайным образом генерируете большое нечетное число, затем проверяете, является ли это число простым, а если нет, генерируете другое случайным образом. Существуют некоторые законы простых чисел, которые в основном утверждают, что ваши шансы "получить" простое число с помощью случайных попыток равны (2 / ln n)
. Например, если вам нужно 512-битное случайное простое число, вы найдете его. дюйм 2 / (512 * ln (2)) Таким образом, примерно 1 из 177 чисел, которые вы попробуете, будет простым.
Есть несколько способов проверить, является ли число простым, один из хороших - это «тест Миллера-Рабина» , как указано в другом ответе на этот вопрос .
Кроме того, в OpenSSL есть хорошая утилита для проверки простых чисел:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Посмотрите, как TrueCrypt это делает. Также обратите внимание на Rabin-Miller для тестирования больших псевдопустых.
Вы не упомянули, какой язык вы используете. У некоторых есть встроенный метод для этого. Например, в java это так же просто, как вызов nextProbablePrime () для BigInteger.
Предыдущий ответ неверен: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Я думаю, что плакат неправильно запомнил (настоящее) доказательство что существует несчетное количество простых чисел.
Mono имеет класс BigInteger с открытым исходным кодом, как и java. Вы можете взглянуть на них. Наверное, портативные :) g'luck