Existe alguma função que gere números primos e inteiros em tamanhos consideravelmente grandes?
Se não, como faze-lo usando JavaScript?
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeUma solução fazendo uso de forge:
var bits = 1024;
forge.prime.generateProbablePrime(bits, function(err, num) {
console.log('número primo aleatório', num.toString(16));
});
Crédito da solução para @dlongley nesta resposta no SOEN.
Eu já insisti o suficiente nos comentários para você usar uma tabela de primos pré-definidos. Gerar primos em JavaScript não é nada eficiente, especialmente se você só precisa sortear um. Se você precisa de números com vários dígitos então, vai ser bem lento.
Segue uma adaptação da implementação do Crivo de Eratóstenes postada pelo usuário Guffa no site Code Review:
function primosAte(n) {
var i, j;
var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;
for (i = 2; i * i < n ; i++) {
if (prime[i]) {
for (j = 0; i * i + i * j < n ; j++) {
prime[i * i + i * j] = false;
}
}
}
var primes = [];
for (i = 2 ; i < n ; i++) {
if (prime[i]){
primes.push(i);
}
}
return primes;
}
var primos = primosAte(1000);
document.body.innerHTML = primos.toString(', ');
Você pode usar uma das bibliotecas nessa página para resolver o seu problema:
A API da biblioteca jsbn lembra bastante as classes java.math.BigInteger
do Java. Por exemplo:
x = new BigInteger("abcd1234", 16);
y = new BigInteger("beef", 16);
z = x.mod(y);
alert(z.toString(16));
vai imprimir b60c
.
BigInteger
, o suficiente para criptografia RSA e não muito mais.BigInteger
.-- Fim da transcrição --
Achei uma implementação de um algoritmo em python
function primosAte(n) {
var i, j;
var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;
for (i = 2; i * i < n ; i++) {
if (prime[i]) {
for (j = 0; i * i + i * j < n ; j++) {
prime[i * i + i * j] = false;
}
}
}
var primes = [];
for (i = 2 ; i < n ; i++) {
if (prime[i]){
primes.push(i);
}
}
return primes;
}
var primos = primosAte(100000000000000000000000000000000000000000000000000000000000000); document.body.innerHTML = primos.toString(', ');
int
,long
oudouble
, algo que demande uma biblioteca de inteiros de precisão arbitrária. E a solução "padrão" para esse problema é sempre a mesma - gerar números aleatórios e testar se são provavelmente primos. O fato desses primos serem "conhecidos" não tem relevância no caso, pois o número deles é grande demais para testar de um por um.