El reto de google

idol_killer · 22-May-2009, 02:00

Este post de Phicar me recordó esto:

Con la intención de contratar a los mejores ingenieros Google publicó este reto:

La traducción:
{primer primo de 10 cifras encontrado en los decimales consecutivos de e}.com

No esperen conseguir un trabajo en Google porque creo q la pagina ya no esta disponible, pero si alguno puede resolverlo agradeceria su ayuda.

Resulta facil escribir un código que diga si un número es primo o no y tambien un código que vaya consiguiendo los numeros de 10 cifras presentes en los decimales de e

Lo dificil es que tal código soporte comprobar un número de 10 CIFRAS!!!
suerte

vit0y4 · 22-May-2009, 11:06

Aca un codigo que me encontre y creo posee algunas fallas... pero no lo probado...
Si ya se que el autor del codigo al final dice que dicho algoritmo deberia correrse en un super-pc... pero quizas colocandole un poco de malicia al codigo y restringiendole el camino, puedes hallar el numero que buscas... es decir lo que planteó google creo que fue un señuelo para atraer gente que estuviese interesada en el tema... ya que no creo que alguien halla podido encontrar el numero en tan poco tiempo... lo interesante es que si buscan alguien interesado en eso es porque buscan un experto en criptografia y Seguridad informatica y por ese lado creo que varios en esta comunidad encajan ... quien sabe quizas si obtengan el trabajo XD hay que ser positivos...

Algoritmo para calcular números primos muy grandes | Kriptópolis

Cita:

class Primo_mas_grande {
public static void main(String Args[]) {
int contador_primos;
double i,j,numero_primo, otro_contador=0;
double primos[] = new double[500];
primos[0]=3;
for(i=7, numero_primo=30/* 2*3*5*/, contador_primos=3/*ya he puesto 3 primos*/, j=1;i<=700;i+=2
/*solo cuentan los números impares*/) {
if(otro_contador==4 ) {
i+=2; /*si el número acaba en 5 se le suma 2*/
otro_contador=0;
}
otro_contador++;
for(int b=0;;b++) {
if(i%primos[b]==0) break;
if(i%primos[b] !=0 && primos[b]>(i/3)) { /*si el numero es menos del triple que otro
el numero es primo*/
contador_primos++;
primos[(int)j] = i; /*si es primo se mete en el array*/
j++;
numero_primo*=i;/*se multiplica el primo por el resultado de la multiplicaciçon de los
primos anteriores*/
break;
}
}
}
numero_primo += 1;
System.out.println("El numero primo obtenido es: "+numero_primo+ " y se ha utilizado un total de
"+contador_primos+" sin contar el 1");
}
}
/*Solo calculo los números hasta 700 porque si meto mas primos no caben en la variable numero_primo*/

Dédalo · 22-May-2009, 17:00

mm no me importa el trabajo en google xD mm ya estoy abriendo el bloc de notas para ver que puedo hacer =) (lo intentaré hacer)

Bueno...

Saludos
Dedalo(Dédalo)

Dédalo · 22-May-2009, 18:47

oigan ya tengo mi respuesta pero no se si es la verdadera alguien que me diga la verdadera :S

Saludos
Dedalo(Dédalo)

perdon por doblepostear....

vit0y4 · 22-May-2009, 18:58

Pon el que tienes !!! o mejor pon tu codigo y lo miramos!!!

Dédalo · 22-May-2009, 19:05

mm bueno miren mi codigo esta basado en el metodo de Sieve mm bueno pues funciona algo asi:

un codigo en python que usa su metodo es este:

Código PHP:


			
def primeSieve(upperBound):
    """
    Returns a list of all prime numbers less than upperBound.
    """
    numbers = range(2, upperBound)
    primes = []
    while numbers:
        prime = numbers.pop(0)
        primes.append(prime)
        numbers = [n for n in numbers if n % prime]
    return primes

mm bueno esta teoria:

Sieve_of_Eratosthenes

mmm el codigo que puso vitoya me sirvio mucho como guia por asi decirlo pero tenia errores mm me ayudo dibujar el problema =) primero lo hice en papel y lo pase a visual basic pero tube unos problemitas asi que lo pase a lo mas parecido casi sin manipular nada solo agregando un par de cositas.... vbs...

Código PHP:


			
Dim a(100000)
d=Round(Sqr(100000))
For z=2 To d
 While a(z)=True
    z=z + 1
 Wend
    i=z * 2
 While a(i)=True
  i=i+z
 Wend
Next
 e="2718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793"
For z=1 To Len(e)-9
 rpta=Mid(e,z,10)
  valida=True
For i=2 To 100000
If a(i)=False Then
     d=CDbl(rpta)/CDbl(i)
If d=Round(d) Then
    valida=False
Exit For
End If
End If
Next
If valida=True Then
  MsgBox rpta 
WScript.Quit
End If
Next

mm bueno el numero que me sale es "7427466391" mm probe poniendo Dedicated Server Hosting | VPS | Domains | Webhosting | Private Racks by LeaseWeb pero no existe :S mm bueno diganme si esta bien mm por sierto recibi un poco de ayuda en la logica matematica por nitrokill el esta aqui en el foro xD...

Saludos
Dedalo(Dédalo)

EDIT: al principio fue un poco frustrante por que lo intente en tres lenguajes aparte de visual basic xD

vit0y4 · 22-May-2009, 20:30

El codigo puesto por dedalo esta perfecto.. sin dudo se ganaria el puesto en Google... XD

Dédalo · 22-May-2009, 20:37

Grax vitoya xD igual ya no esta vigente creo xD ya ha salido nuevos segun lo que vi en el mismo google =)... tubo muchos errores como for en lugares donde no ivan cosas pequeñas pero que joden xD mm despues lo que te dije Len(e)-9 ahi tb me confundi xD mm pero creo que ya esta bien o por lo menos en logica ya esta bien =)

Saludos
Dedalo(Dédalo)

Tronador · 04-Jun-2009, 17:21

No creo q den el trabajo asi de facil, de hecho yo puse a unos alumnos de Programacion I (soy monitor) a que lo resolvieran y muchos pudieron hacerlo sin ningun problema xD

Dédalo · 04-Jun-2009, 18:33

mm mira no fue tan dificil pero Programación 1??? mmm pos que lenguaje les enseñan??? por que no todos te resisten contar asi los decimales =S y tienes que tener un buen conocimiento matematico por que el Valor de e no es tan facil de conseguir =S mm bueno no se igual si no es tan dificil =)

Saludos
Dedalo(Dédalo)