Well, this challenge is in english for do harder.
Lekeness easy but it isn't.
This algorithm must recognize and returned if number cousin or not.
I find the fast.
I do benckmarck's (measuring the time)
Help:
All number compound(not cousin) must meet the next:
n=d*q if 2<= d <= t /n=t*t
Good Luke!!!
Suscribirse a:
Enviar comentarios (Atom)
8 comentarios:
eso no es ingles de un ingles, eso es ingles de un argentino :P
creo q voy a hacer el unico en postear :S
bueh, veamos... primo..., uso esto yo:
http://es.wikipedia.org/wiki/Peque%C3%B1o_Teorema_de_Fermat
aca mi codigo xD, el primero que programo bajo linux, nada diferente con windows xD
#include stdio.h /*no uso los triangulitos sino no se ve nada xD*/
#define pow(a,b) pow_(a,b - 1,a)
int pow_(int a, int b, int c)/* uso mi pow, creo deberiamos usar nuestras propias funciones aveces..., en este caso por divercion xD*/
{
if(b == -1 && a == c)
return 1;
b--;
a *= c;
return b == 0 ? a : pow_(a, b, c);
}
main()
{
unsigned int prim;
do{
puts("Ingrese un numero (entero mayor que 1)");
scanf("%i", &prim);
}while(!prim || prim == 1);
if((pow(2, prim) - 2 ) % prim == 0){
printf("primo\n");
return 0;
}
printf("no-primo\n");
}
Guau!
(Es una gran verdad los sensillos algoritmos salen de formulas matematicas)
http://es.wikipedia.org/wiki/Test_de_primalidad
yo lo pense para numeros muuy grandes, y que en ves de buscar el boton 'run' busque el que diga 'fly'.
[code]__int64 dprimo(__int64 n){
__int64 d=2;
while(d*d<=n){
if(!(n%d))return d;
++d;
}
return 0;
}[/code]
solo queda benchmark de juez.
ajam, osea, el mio es una mierda xD
si, el tuyo es mas rapido, porque si queremos saber si 1000 es primo, multiplica 1000 veces a 2, y en tu caso lo hace menos veces (por eso de d*d)
felicitaciones xD
y... no es un foro, los [code] no funcionan aca xD
cada algoritmo tiene su fundamento.
el mio por el señor ibn al-Banna, el tuyo por fermat.
Que un algoritmo es mas rapido que otro para una cierta entrada es verdad.
(ejemplo ordenar un vector, segun los matematicos el mejor es el quick sort, ...sabias que si solo esta desordenado los dos ultimos elementos, uno más pero como el burbuja le ganaria ampliamente.)
Quiero provar los dos algoritmos para un numero dificil para el mio.
Probabilidad:
(2^p) -1= es muy probable que sea primo.
p=61
(2^p) -1= 251...(18 cifras)
cuantos ciclos hara (max) el mio 1,5 mil millones
Hipotecis Pre-benchmarck
Fijate (en mi codigo)que cuanto mas grande sea n con respecto a d, mas le cuesta hacer el mod. ( la velocidad del while va aumentando ¿pero lo que demoro hasta llegar hasta vel suficiente?)
Bueno el tuyo ..., confieso que modificare a pow por un for , por que: llamar b veces a pow y retornar b veces es disparatado porque pasaras por valor 64 bits b*2 veces.
Hay ganara muuy mucho tiempo.
Te paso el codigo que queda y hago benchmarck con el dev al mio. luego si te agrada la mejoria hago benchmark al tuyo.
No se cual ganará.
Default tecnico, por ese camino no podras a menos que conoscas como manejar en c o fortran un numero de mas de 100 dijitos.
[code]#include "stdio.h"
int main()
{
unsigned __int64 prim=61;//estoy acotado de 0 a 64, para el supuesto primo
//porque 2^64 es el numero maximo que soporta las variables de 64bit
//fermat: Si [(2^p)-2]mod p es 0 si p es primo
//Lo que esta entre corchetes tiene muchisimos mas digitos que el supesto primo en si
unsigned __int64 aux=1;
unsigned __int64 aux2=1;
for(;prim; --prim)aux*=2;//61 veces
--aux;
aux2=aux;
for(;aux2; --aux2)prim*=2;//2^61 veces
prim-=2;
if(!(prim)%aux)printf("PRIMO");
else printf("No-primo");
getch();
return 0;
}
[/code]
pongo eso hasi sobreesplico donde empieza y finaliza
pero....supongo que con muuucha memoria se resolveria.
quedaria... para 20 cifras, lo sig
#include windows.h
#include stdio.h
int main()
{
unsigned __int64 n=2305843009213693951;
unsigned __int64 d=2;
long final,inicio = GetTickCount();
while(d*d<=n){
if(!(n%d))break;
++d;
}
final = GetTickCount();
if(d*d<=n) printf("NO-es primo, el divisor es enorme \n");
else printf("PRIMO \n");
final-=inicio;
printf("El tiempo fue....%u [ms]",final);//milisecond
getchar();
return 0;
}
el ejemplo lo resuelve en 79907 milisegundos (80seg).
Numero maximo:
18.446.744.073.709.551.615
Valla Dreams_Eater, no cabe duda que te encanta la programación, al igual que niO, eso es bueno.
Bueno dreams_eater sincceramente te deseo lo mejor , te deseo que siempre conserves la esperanza y la fe en ti y en tus posibilidades, para hacer de tu vida aquello de lo que te sientes capaz.
Saludos..
Att: Delfi
Si esque aun me recuerdas..
Coincido con Delfi.
Y yo también te deseo lo mejor, puede que tu no me recuerdes, pero yo aún recuerdo el antiguo staff de Inside-System (casper, b@cHo, fran...) del cual Delfi también formaba parte.
Me alegra volver a saber de ti, espero que tu blog tengo mucho éxito.
Atte.RED FOX/Sknight (moderaba la sección de hardware)
Ps. Delfi, que bueno saber que sigues bien :)
Publicar un comentario