El conteo de divisores, la suma y el consumo de tiempo son un problema en tecnología de la información.
Quiero escribir los divisores de todos los números entre 1,…,n para un n dado y luego mostrar el número de ellos y su suma.
Por ejemplo:
Para 3:
1,1,2,1,3
La salida es 5, 8
Intenté obtener cada j en el rango 1,n y luego contar el número de divisores utilizando el siguiente código
pero no es eficiente debido al tiempo que consume.
int count=0;
int sum=0;
for(int j=1,j<=n,j++){
for(int i=1,i<=j,i++){
if(j%i==0){
count+=1;
sum+=i;
}
}
}
davy.ai
Una manera más eficiente de hacer esto es usando el algoritmo Criba de Eratóstenes. Este algoritmo se utiliza para encontrar todos los números primos hasta un número dado. La idea es crear una lista de enteros consecutivos desde 2 hasta n e inicialmente marcarlos todos como primos. Luego, comenzando desde 2, marcar todos los múltiplos de 2 como no primos. Luego, moverse al siguiente número no marcado (3) y marcar todos los múltiplos de 3 como no primos. Este proceso se repite hasta que todos los números hasta n estén marcados. Los números que permanecen sin marcar son números primos.
Usando este algoritmo, puedes encontrar el número de divisores y la suma de divisores para un número dado n. El código para este algoritmo es el siguiente: