## 10820 - Send a Table

Moderator: Board moderators

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
Ac but not satisfied with the time.
I used medv's function to calculate the no. of relative primes for a number i. and then
result=result[i-1]*2*no_of_relative_primes(i);
I precalculated 1 to 50,000 before scanning any input.
Then i just print the result[n] for each input n.
But it took 0.277 seconds. How do i improve the time?

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
AC in 0.12 but still not satisfied.
I am now not using medv's function but a variant of sieve.
I calculate totient function for all n from 1 to 50,000.
Then I calculate all answers from 1 to 50,000.
Then i just scan and print the apropriate answer from the array.

Please suggest a better method. How to get 0.002?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Either use a faster sieve, or just compute result+=result[i-1], and for each input n, output result[n]*2-1

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result+=result[i-1]+result<<1 and just printing result[n] seems similar to what you suggest. I can't see what computational advantages your method has.

Below is my code for calculating totient using sieve:-

Code: Select all

``````for(i=1;i<50001;i++)
nrp[i]=i;
for(i=2;i<50001;i++)
if(nrp[i]==i)
{
nrp[i]--;
for(j=i<<1;j<=50000;j+=i)
nrp[j]=nrp[j]*(i-1)/i;
}
``````
And this is my code for calculating result:-

Code: Select all

``````last = ans[1] = 1;
for(i=2;i<=50000;i++)
last = ans[i] = last + (nrp[i]<<1); // variable last is used instead of ans[i-1] just to save a few memory accesses
``````
I would appreciate if you could suggest some ways to improve above functions.

panhantao
New poster
Posts: 2
Joined: Tue Aug 14, 2012 6:00 pm

### Re:

sandy007smarty wrote:@sclo:
1. Is their some faster sieve algo? Can you provide some links?
2. Calculating result+=result[i-1]+result<<1 and just printing result[n] seems similar to what you suggest. I can't see what computational advantages your method has.

Below is my code for calculating totient using sieve:-

Code: Select all

``````for(i=1;i<50001;i++)
nrp[i]=i;
for(i=2;i<50001;i++)
if(nrp[i]==i)
{
nrp[i]--;
for(j=i<<1;j<=50000;j+=i)
nrp[j]=nrp[j]*(i-1)/i;
}
``````
And this is my code for calculating result:-

Code: Select all

``````last = ans[1] = 1;
for(i=2;i<=50000;i++)
last = ans[i] = last + (nrp[i]<<1); // variable last is used instead of ans[i-1] just to save a few memory accesses
``````
I would appreciate if you could suggest some ways to improve above functions.
well,actually i don't quite understand your codes , but i can share my pre-calculating codes, which i used getting ac in 0.012sec

Code: Select all

``````const int MAXN = 50005;
bool isPrime[MAXN+5];
int phi[MAXN],farey[MAXN];

void init()
{
// generate prime numbers
memset(isPrime,true,sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for(int i = 2; i*i <= MAXN; i ++)
if(isPrime[i])
for(int j = i; j*i <= MAXN; j ++)
isPrime[i*j] = false;

// because phi(i) = i*(1-p1/p1)*...*(1-pk/pk), you can generate the phi[] array similar to the way we generate prime numbers
for(int i = 1; i <= MAXN; i ++) phi[i] = i;
for(int i = 2; i <= MAXN; i ++)
if(isPrime[i])
for(int j = i; j <= MAXN; j += i)
phi[j] = phi[j]/i * (i-1);

// sum up phi[i] to farey[i]. obiously, the answer for a given N would be (2*farey[N]-1).
farey[1] = 1;
for(int i = 2; i <= MAXN; i ++)
farey[i] = farey[i-1] + phi[i];
}
``````