[Leusss]

Hola de nuevo. Tengo un problema al tratar de hacer un programa que calcule la funcion totient (o phi) de Euler hasta cierto número (necesito entre 10000 y 100000 particularmente) utilizando esta fórmula:

Si \( p_1,p_2,...,p_k \) son todos los divisores primos de n entonces:
\( \phi(n) = n*\displaystyle\prod_{i=1}^{k}{(1-\displaystyle\frac{1}{p_i})} \) (no considero al 1 como primo)

Y el problema que tengo es que quiero hacer un arreglo que guarde un 1 o un 0 en cada posición, en el caso en que el número de esa posición sea primo (es decir array[3] = 1, array[4]= 0, array[5] = 1, etc...); pero si defino este arreglo adentro de la funcion phi, lo va a tener que calcular cada vez que quiera usar la función y esa no es la idea. Mi idea es tenerlo en algún lugar del programa que sea "accesible" a cualquier función, pero no sé como hacerlo :S. Lo trate de definir en la función main pero no me deja llamarlo desde la función phi...

¿Se entiende más o menos lo que pido ?

EDIT: Me olvidé de aclarar que el lenguaje es C

[topo23]

Algo asi deberia funcionar

Código: [Seleccionar]

int primos[1000000];

int phi_euler()
{
   // ..
   primos[2] = primos[23]=1;
   return 0;
}

int main()
{
   // ..
   primos[2] = primos[23]=1;
   return 0;
}

No se que compilador/sistema operativo usas, pero puede suceder que no compile/ejecute porque no tiene suficiente espacio de pila.

La forma de solucionar eso es utilizar la memoria del heap con malloc/free.

Código: [Seleccionar]

int* primos;

int phi_euler()
{
   // ..
   primos[2] = primos[23]=1;
   return 0;
}

int main()
{
   primos = (int*)malloc((1000000)*sizeof(int)); // antes de cualquier operacion que use primos
   // ..
   primos[2] = primos[23]=1;
   free((void*)primos); // cuando no se va a usar mas y antes de salir
   return 0;
}


[Leusss]

Hola, gracias por la respuesta y perdón por mi respuesta tardía.

Problemas de memoria no hubo Así que lo que hice fue simplemente declarar el arreglo "afuera" y construirlo en la función main (anduvo de primera). De todas maneras pongo el código acá, porque debe ser muy mejorable. El trabajo ya lo entregué de todos modos, pero si alguno tiene una mejora me vendría bien para saber

El ejercicio era: Encontrar el número "n" de 5 cifras para el cual el cociente \( \displaystyle\frac{n}{\phi(n)} \) es máximo.

Código: [Seleccionar]

#include <stdio.h>

char primos[100001];
main()
{
int i, j, k, m;
float max[2];
float cociente;
max[0]=max[1]=0;

primos[0]=primos[1]=0;
//Criba de eratostenes
for(i=2;i<=100000;++i)
primos[i]=1;

for(j=2;j*j<=100000;++j)
        if(primos[j])           
                       for(k=j*j;k<=100000;k=k+j)           
                                                primos[k]=0;
//Prueba con todos y devuelve el maximo cociente
for(m=10000;m<100000;++m){
cociente=m/(float)phi(m);
    if(cociente>max[1]){
                       max[0]=m;
                       max[1]=cociente;
                       }
}
printf("Numero: %.0f\t Cociente: %f\n", max[0], max[1]);

}

int phi(int x)
{
int i, c=x, phi=x;
if(x==2) return 1;
if(primos[x]) return x-1; //Formula para los primos                           
/*Dado un x no-primo, los numeros que aportan a la formula son los primos de la descomposicion
de x. Este bucle lo que hace es encontrar uno de ellos, dividir tantas veces
como pueda a x, y cuando ya no puede mas pasa al siguiente.
Lo hice para asegurarme que los numeros que "aporten" a la formula sean
todos primos*/   
if(c%2==0){                                             
          phi/=2;
          while(c%2==0)
                       c/=2;
          }
for(i=3;i<=c;i+=2)
                    if(c%i==0){
                               phi=(phi*(i-1))/i;
                               while(c%i==0)
                                            c/=i;
                     }                        
                           
return phi;
}


[topo23]

Es posible ver que \( \displaystyle\frac{n}{\phi(n)}=\prod_{i=1}^k \frac{p_i}{p_i - 1} \), donde \( \displaystyle n = \prod_{i=1}^k p_i^{\alpha_i} \) es la descomposicion en primos de n.

De aqui puedes observar que como \( \frac{p_i}{p_i-1}>1 \) te conviene que el numero n tenga muchos primos diferentes. Como estas limitado a 5 cifras y si un primo aparece varias veces en la factorizacion aporta solo una vez al cociente te conviene que no haya repetidos. Ademas como \( p < q \Longrightarrow \frac{p}{p-1} > \frac{q}{q-1} \) te conviene que la descomposicion aparezca la mayor cantidad de numeros primos chicos.

Con todo esto una forma de encarar el problema es empezar a multiplicar todos los primos 2.3.5.7.11...., hasta obtener el mayor un numero de cinco digitos (si no me equivoco es 30030). En caso de que no obtengas un numero con la cantidad de digitos que esperas lo que puedes hacer es quedarte con el inmediato anterior, y multiplicar por aluguno de los factores (por ejemplo 2) hasta obtener la cantidad de digitos necesarias.

[Leusss]

Jaja muy buena la idea, no me había puesto a "analizar con hoja y papel" la fórmula del cociente. Pasa que a veces temo que reducir mucho el problema mediante métodos matemáticos. haga que el programa termine siendo medio obsoleto. Pienso "para qué me piden el programa si se puede resolver mayormente a mano".