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

## 10914 - Abundance and Perfect Numbers

**Moderator:** Board moderators

### 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.

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.

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.

I tried time attack, and got 0.287 sec.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.

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.

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 ; } } }
```