10914 - Abundance and Perfect Numbers

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Jan 15, 2006 12:47 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

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

10914

Post by Sedefcho » Tue Feb 06, 2007 2:06 pm

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
Location: Calgary, Canada

Post by Darko » Tue Feb 06, 2007 8:42 pm

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 07, 2007 5:10 am

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.

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

Post by Sedefcho » Wed Feb 07, 2007 10:57 am

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

Post by Grazyna » Tue May 01, 2007 3:00 pm

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 received about 10-20 times TLE.
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[10000100] = {0} ;
long maxn=10000100 , prime[350000] ;
long long sum ;
bool primeQ ;    
long np , n , k , i , m ;

m=6 ; while(m<maxn) { abud[m]=1 ; m=2*m ; }
prime[0]=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 ; } } }



Post Reply

Return to “Volume 109 (10900-10999)”