## 10914 - Abundance and Perfect Numbers

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I did *almost* the same thing, but I generated sums at the same time I generated almost odd primes (AOPs). Every sum depends on AOP and the previous sum.

I am not sure why you are sorting numbers, mine are sorted when I'm done with the generating part. I basically went through all even numbers, counted the number of shifts needed to get an odd number out of them and checked if the remaining odd number is prime.

That resulted in <1sec.. in Java! Darko

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### 10914

Darko, I just managed to get ACC in Java but my
program runs on the Judge for about 5.500 secs.

I don't see anyone with an ACC solution in Java
faster than mine It's probably because you
also have a C++ solution which is faster so the
Judge ranks you using that solution.

Do you mean 1 sec in Java on the Judge machine ?
Or do you mean 1 sec in Java on some other machine ?
If you have < 1 sec on the Judge I am quite curious how
you achieved that. It should be some quite good and
quite optimized Java code.

This one ( 10914 ) is a really nice problem.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Yes, 1 sec on UVa:
http://acm.uva.es/problemset/statusjudge.php?u=19882

Java is not important there, I think the rest of it is. I recoded it in C and it ran in 0.8 secs. I will send you the code in PM.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Solaris wrote:I got AC in about 2 seconds, but in the ranklist I saw quite a few ppl solving it in less than 1 sec. Can anyone give me a hint on the better solutions? I am unable to find a trick myself My approach to the problem is as follows:

1. Generate all primes upto 5000000
2. Getting the almost prime numbers. (Each almost prime no is of the form 2^n * primeNumber)
3. Sort the numbers
4. Run a loop through the array to precalculate the abundance value.
5. Binary search to get abun(n) for any given n

I will be very happy if anyone gives me a hint about his/her better solution. Thanks in advance.
I tried time attack, and got 0.287 sec.
In my approach, I didn't precalculate the abundance value and calculate theabundance value for each input.
Precalculating the hole abundance value takes too much time.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I precalculate the abundance values OK, thank you all for the replies.

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece
I follow the strategy that it was written above.

1.calculate all primes till 5000000 and at the same time filling a sieve with almost odd numbers,
2 when reading from the input n, calculating the sum till n

I have no idea how to make it faster.
Thanks in advance for any suggestions.

here is the code of my precalculations:

Code: Select all

``````
bool abud = {0} ;
long maxn=10000100 , prime ;
long long sum ;
bool primeQ ;
long np , n , k , i , m ;

m=6 ; while(m<maxn) { abud[m]=1 ; m=2*m ; }
prime=3 ; np=1 ;
for(n=5 ; 2*n<maxn ; n+=2) {
primeQ=true ;
for(i=0 ; prime[i]*prime[i]<=n ; i++)
if (n%prime[i]==0) { primeQ=false ; break ; }
if (primeQ) {
prime[np++]=n ;
m=2*n ; while(m<maxn) { abud[m]=1 ; m=2*m ; } } }

``````