Phicar's world

Hola muchachos, hoy les presento la funcion para determinar la funcion phi de un numero n...junto a esta funcion les presento dos formas de determinar si un numero es primo(ya lo vi por ahi en posts de monje y radical..pero no quiero dannar la estructura del post)..despues les mostrare otros teoremas mucho mas avanzados..miller rabit..fermat bueno entre otros..para terminar por factorizacion de numeros primos como el metodo de monte carlo ya que por el momento no me se mas ...Bueno para empezar...

Que carajo es un numero primo??

un numero primo es el cual solo es divisible por si mismo y por 1..

Que carajo es la funcion phi???

Phi aunque es prefijo de un nick de un personaje muy chevere xDDD mentiras...la funcion phi es una funcion para buscar los numeros menores o igual a n donde no contengan ningun factor comun..

Como funciona la funcion Phi??

bueno la funcion phi funciona de esta manera...primero se evaluea si el numero n es primo pues todos los numeros exceptuando si mismo va a ser primales a n..o sea que
{Phi(n)=(n-1) | n sea un numero primo}
si n no es primo entonces se procede a buscar los factores primos de n..

y la respuesta seria (n)*(1-(1/p_k))...tal que p_k son los factores primos de n....


No siendo mas les dejo mejor codigo(java me encanta Java )

Metodo uno para determinar si un numero es primo

public static boolean isPrime(double n){
if(n==2 || n==3) return true;//2 y 3 son primos
if(n%2 == 0) return false;//si es par no es primo
if(n<2) return false;//0 y 1 son una vaina rara
for(double a=3;a<=(n/2);a+=2)//valla por los numeros impares hasta el maximo numero que puede dividir a n(su mitad :))
if(n%a==0) return false;//si resulta que el residuo de alguna de esas divisiones es 0 entonces no es primo
return true;//si no pasa nada entonces es primo

Funcion phi

public static double phi(double n){
Vector<Double> num = new Vector<Double>();//es como un arreglo dinamico*
if(isPrime(n)) return(n-1);//si es primo como dijimos devuelve el numero -1
double res = n;//donde voy a empezar a iterar los factores
if(n%2 == 0) num.add(2.0);//si es par tiene un dos por ahi
for(double a = 1;a<=(n/2);a+=2)//valla buscando todos los impares hasta su mitad
if(n%a == 0 && isPrime(a))num.add(a);//si el numero es divisible por n y aparte es primo lo agnado a el vector
for(int r = 0;r<num.size();r++)//ahora recorro el vector
res*=(1-(1/(num.get(r))));//y multiplico n por (1-(1/p[sub]k[/sub])) como dice la funcion
return res;//retorno la multiplicacion
}

*dinamico es que crece en tiempo de ejecucion

Mi funcion consentida en la generacion de primos...la criba de erastotenes

boolean num[] = new boolean[x];//x es el numero-1 hasta el cual quieren generar primos
Arrays.fill(num,true);//esto viene en java.util, relleno todo de true
num[0]=false;
num[1]= false;//como dije 0 y 1 son vainas raras
for(int n = 2;n<=Math.sqrt(num.length);n++){//recorro hasta la raiz cuadrada de la longitud del arreglo
if(num[n]) 
for(int k = n*n;k<num.length;k+=n) num[k]=false;//recorro todos los multiplos de n numero y digo no son primos
}

//esto ya es pa imprimir algun resultado

for(int n=0;n<num.length;n++)
if(num[n]) System.out.println(n);//eso imprimiria todos los numeros primos hasta x :)

Esperen las otras partecitas chao