Un número redivisible es aquel que es divisible entre su número de divisores positivos. Por ejemplo 1(1 divisor), 12(6 divisores) y 9(3 divisores) pero no 7(2 divisores) ni 16(5 divisores)
Escribe un programa que dados dos enteros l y h, diga cuántos números refactorizables hay entre l y h, inclusive.
/**
ResponderEliminar* Solución al problema Redivisible de la omi traning gate
* @author: Catalina Valencia Hernández
* Facultad de Ciencias UNAM
*/
#include
long long criba[2000000];
long long cont=1,l,h;
long long div=1,pre,aux;
//Calcula la cantidad de divisores de un número m
void fac(long long m)
{
while(criba[m]!=0)
{
pre=criba[m];
m/=criba[m];
if(pre==criba[m])
cont++;
else
{
div*=(cont+1);
aux=cont;
cont=1;
}
}
if(m!=pre)
{
cont=1;
div*=(cont+1);
}
else
{
div/=(aux+1);
aux++;
div*=(aux+1);
}
}
int main()
{
scanf("%lld %lld",&l,&h);
criba[1]=1;
//Obtiene los numeros primos hasta 2000000
for(long long i=2;i*i<=2000000;i++)
{
if(!criba[i])
{
for(long long j=i*i;j<=2000000;j+=i)
{
if(!criba[j])
criba[j]=i;
}
}
}
long long k=0;
//Obtiene la cantidad de números redivisibles entre l y h inclusive
if(l==1)
{
k++;
l=2;
}
for(int i=l;i<=h;i++)
{
div=1;
cont=1;
fac(i);
if(i%div==0)
k++;
}
printf("%lld",k);
return 0;
}
#include
ResponderEliminarlong long l,h,a[2000001][5],j,r,k,i;
int main(){
scanf("%lld %lld",&l,&h);
a[1][2]=1;
a[2][3]=1;
a[1][3]=1;
for(i=2;i<h+1;i++){
if(a[i][0]==0){
a[i][2]=2;
for(j=i;j<h+1;j=j+i){
a[j][0]=1;
a[j][1]=i;
}
for(k=i*i;k<h+1;k=k+(i*i))
a[k][0]=2;
}
if(a[i][0]==1){
a[i][2]=2*a[(i/a[i][1])][2];
if(i%a[i][2]==0)
a[i][3]=1;
}
if(a[i][0]==2){
a[i][0]=a[(i/a[i][1])][0]+1;
a[i][2]=((a[i][0]+1)*a[i/a[i][1]][2])/a[i][0];
if(i%a[i][2]==0)
a[i][3]=1;
}
}
for(i=l;i<h+1;i++){
if(a[i][3]==1){
r=r+1;
// printf("%ld %ld %ld %ld\n",i,a[i][2],a[i][1],a[i][0]);
}
}
printf("%lld",r);
}