## 11411 - MiniMice

**Moderator:** Board moderators

### 11411 - MiniMice

Hi,

I am currently working on the MiniMice problem. My strategy is to first find all primes from 1 to 5000000, then all divisors of n for 1 <= n <= 5000000, store all of these in arrays, and then proceed with finding what the question asks for.

My problem is that I can't seem to find an algorithm efficient enough to run in under 6 seconds to find all the divisors. I am finding the primes by checking to see if n is divisble by any primes up to sqrt( n ). Then I'm finding all divisors by dividing n by the same prime until it can no longer be divided by that prime. In other words using the fact that for b1^(c1)*b2^(c2)*...bn^(cn), that there are (c1+1)(c2+1)...(cn+1) divisors.

Now, either my algorithm isn't efficient, or I'm doing a lot of extra stuff that I don't need to be doing. I don't see any more efficient manner in which to find all the divisors, so it's probably that I don't need to do all of this, and there's another way.

Can anybody offer some help?

Thanks.

I am currently working on the MiniMice problem. My strategy is to first find all primes from 1 to 5000000, then all divisors of n for 1 <= n <= 5000000, store all of these in arrays, and then proceed with finding what the question asks for.

My problem is that I can't seem to find an algorithm efficient enough to run in under 6 seconds to find all the divisors. I am finding the primes by checking to see if n is divisble by any primes up to sqrt( n ). Then I'm finding all divisors by dividing n by the same prime until it can no longer be divided by that prime. In other words using the fact that for b1^(c1)*b2^(c2)*...bn^(cn), that there are (c1+1)(c2+1)...(cn+1) divisors.

Now, either my algorithm isn't efficient, or I'm doing a lot of extra stuff that I don't need to be doing. I don't see any more efficient manner in which to find all the divisors, so it's probably that I don't need to do all of this, and there's another way.

Can anybody offer some help?

Thanks.

### Re: 11411 - MiniMice

My method is not very efficient, but managed to get accepted.

The fact is for any n we don't need all the divisors , but wee actually need the number of divisors. Number of divisors can easily be found using sieve (idea).

Then I took all the number of divisors for each i (for i = a to b). Sort them using

The fact is for any n we don't need all the divisors , but wee actually need the number of divisors. Number of divisors can easily be found using sieve (idea).

Then I took all the number of divisors for each i (for i = a to b). Sort them using

**counting sort (idea)**. Then used greedy.Ami ekhono shopno dekhi...

HomePage

HomePage

### Re: 11411 - MiniMice

Code: Select all

```
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main()
{
//find all primes;
vector< int > primes;
primes.reserve( 400 );
primes.push_back( 2 );
for( int i = 3; i * i <= 5010000; i += 2 )
{
bool a = true;
for( unsigned int j = 0; j < primes.size() && primes[ j ] * primes[ j ] <= i; ++j )
{
if( i % primes[ j ] == 0 )
{
a = false;
break;
}
}
if( a )
primes.push_back( i );
}
int num;
cin >> num;
for( int m = 0; m < num; ++m )
{
int a, b;
cin >> a >> b;
int divs[ 400 ];
for( int i = 0; i < 400; ++i )
divs[ i ] = 0;
//find all divisors in the range, using idea that
//a maximum of 2 of each number of divisors is
//needed because after that difference is 0
for( int i = a; i <= b; ++i )
{
int temp = i;
int total = 1;
int count = 1;
int index = 0;
for( int j = primes[ index ]; j*j <= temp; j = primes[ ++index ] )
{
/* for( int temp2 = temp / j; temp2 * j == temp; ++count )
{
temp = temp2;
temp2 = temp / j;
}*/
while( temp % j == 0 )
{
++count;
temp /= j;
}
total *= count;
count = 1;
}
if( temp != 1 )
total *= 2;
if( divs[ total ] < 2 )
divs[ total ]++;
}
//finds the maximum difference, could be improved
//by getting rid of the deque but the time this takes
//to run is really insignificant since its a max of less
//than 800 pushes
deque< int > sorted;
bool inFront = true;
for( int i = 0; i < 400; ++i )
{
if( divs[ i ] == 2 )
{
sorted.push_back( i );
sorted.push_front( i );
}
if( divs[ i ] == 1 )
{
if( inFront )
{
sorted.push_back( i );
inFront = false;
}
else
{
sorted.push_front( i );
inFront = true;
}
}
}
sorted.push_back( sorted.front() );
int sortsize = sorted.size() - 1;
int maxt = 0;
for( int i = 0; i < sortsize; ++i )
{
int t = abs( sorted[ i ] - sorted[ i + 1 ] );
if( t > maxt )
maxt = t;
}
cout << maxt << endl;
}
return 0;
}
```

**sieve (idea)**,

**counting sort (idea)**, and

**greedy**in your post. Could you please explain?

### Re: 11411 - MiniMice

Ok, I got it to work by using the sieve idea. This got rid of all the divisions and multiplications in my loops.

### Re: 11411 - MiniMice

About the sieve idea:t_sergiu wrote:This is the way that I have it right now. I don't know what you mean bysieve (idea),counting sort (idea), andgreedyin your post. Could you please explain?

You don't have to store the primes. But when calculating the primes you can update the multiples.

Code: Select all

```
factor[i] = 1; // for all i
for(i=2;i<MAX;i++) if(i is a prime)
for(j = all multiples of i)
{
find x // x is the largest number, j is divisible by i^x
factor[i] = factor[i] * (x+1);
}
```

Now for any input take all the factors from a to b and store them in another array say a[]. Then my method requires to sort them. Now since there can be so many numbers O(n*log(n)) sorting will give you TLE. But we can see that the range of factors is small. So, O(n) sorting is possible (this is the counting sort idea).

Then try to figure out how the numbers should be taken such that the maximum difference is minimized. Hope these help.

Ami ekhono shopno dekhi...

HomePage

HomePage

### 11411 - MiniMice

PLZ HELP .THIS CODE GIVE WA

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#define max 5000000

long prime[max+1],lod[ max+1];

void facto()

{

long i,j,temp,ss,count;

for(i=2;i<=max;i++)

{

if(prime

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#define max 5000000

long prime[max+1],lod[ max+1];

void facto()

{

long i,j,temp,ss,count;

for(i=2;i<=max;i++)

{

if(prime

*==0)*

{

temp=i;

prime{

temp=i;

prime

*=2;*

for(j=2*i;j<=max;j+=i)

{

count=1;

ss=j;

while(ss%temp==0)

{

ss/=temp;

count++;

}

if(prime[j] != 0)

{

prime[j]*=count;

}

else

{

prime[j]= count;

}

}

}

}

}

int main()

{

facto();

long i,j,test,a,b,f,s;

scanf("%ld",&test);

while(test--)

{

scanf("%ld %ld",&a,&b);

f=-1;

s=-1;

for(i=a;i<=b;i++)

{

if(f<primefor(j=2*i;j<=max;j+=i)

{

count=1;

ss=j;

while(ss%temp==0)

{

ss/=temp;

count++;

}

if(prime[j] != 0)

{

prime[j]*=count;

}

else

{

prime[j]= count;

}

}

}

}

}

int main()

{

facto();

long i,j,test,a,b,f,s;

scanf("%ld",&test);

while(test--)

{

scanf("%ld %ld",&a,&b);

f=-1;

s=-1;

for(i=a;i<=b;i++)

{

if(f<prime

*)*

{

s=f;

f=prime{

s=f;

f=prime

*;*

}

else

{

if(s<prime}

else

{

if(s<prime

*&& f!=prime**)*

{

s=prime{

s=prime

*;*

}

}

}

printf("%ld\n",(f-s));

}

return 0;

}

WHERE IS MY WRONG ????}

}

}

printf("%ld\n",(f-s));

}

return 0;

}

WHERE IS MY WRONG ????

### Re: 11411 - MiniMice

# Search the board first!

# Don't create a new thread for a problem for which one already exists.

# Use code tags when posting codes.

# Don't create a new thread for a problem for which one already exists.

# Use code tags when posting codes.