problem divsum in spoj

[vineet gandhi]

hello everyone !!
after a long time.
in the divsum problem i have used sieve of erathno.....
if talking about iimplemntation while eliminating the non primes i
inserted an if statement to check whether the given no. is divisible
by that non prime no. since sieve of eratno.....
eliminates duplicacy so the check is performed once.
and while printing the no.s
i have again inserted a check on the given no by the obtained prime
no.s
so adding the two sum obtained.
the code is running write but when submitting giving TLE may be
because of large I/O
PLEASE SUGGEST .
I WILL POST THE CODE IF REQUESTED.

[anoop chaurasiya]

better u paste the code with problem link..

--
Anoop Chaurasiya
CSE (2008-2012)
NIT DGP

[vineet gandhi]

import java.util.Scanner;

/**
*
* @author roger
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner s=new Scanner(System.in);
int sum=0;
int ad=s.nextInt();
while(ad>0)
{
int x=s.nextInt();
boolean flag[]=new boolean[x+1];
int z=(int) Math.sqrt(x);

for(int a=2;a<=z;a++)
{ for(int j=a*a;j<=x/2;j=j+(2*a))
{
flag[j]=true;
if(x%j==0)
{
sum = sum + j;

}
if(a==2)
{j=j+a;
}
}
}

for(int k=1;k<=x/2;k++)
{if(flag[k]==false)
{if(x%k==0)
{sum=sum+k;
}

}

}


System.out.println(sum);
ad--;
sum=0;
}
}
}
i have written in java but I have not used library functions
suggest faults and other alternatives also.

On May 18, 12:23 pm, anoop chaurasiya <anoopchaurasi...@gmail.com>
wrote:

> NIT DGP- Hide quoted text -
>
> - Show quoted text -

[ANUJ KUMAR]

go till square root of x rather than x/2

[vineet gandhi]

this is the problem link http://www.spoj.pl/problems/DIVSUM/
and since we have to find the sum of divisors not the primes we don't
need to go to x ,=x/2 is sufficient
this is my revised code

import java.util.Scanner;

/**
*
* @author roger
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner s=new Scanner(System.in);
int sum=0;
int ad=s.nextInt();
while(ad>0)
{
int x=s.nextInt();
boolean flag[]=new boolean[x+1];
int z=(int) Math.sqrt(x);

for(int a=2;a<=z;a++)

{ if(flag[a]==true)
{a++;}
int j=a*a;
while(j<=x/2)
{flag[j]=true;
if(x%j==0)
{sum=sum+j;
}
if(a==2)
{j=j+a;
}
else
{j=j+(2*a);}

> >> - Show quoted text -- Hide quoted text -

[anoop chaurasiya]

i think u need to re-analyse seive of erathan... more deeply, [ a trivial thing u are missing here is that divisors always come in pairs so once u find a divisor say d less than sqrt(n) u can find its complementary one as n/d,so sqrt(x) will serve our purpose instead of x/2...(do take care of perfect squares)].

one more thing i would suggest u to use C instead of java as far as spoj is considered.

[vineet gandhi]

thanks a lot bhaiya please suggest more questions on sieve to make it
strong.

On May 19, 1:18 pm, anoop chaurasiya <anoopchaurasi...@gmail.com>
wrote:

[Amisha Bansal]

I posted this for the divsum problem. I made it in C. But it shows compilation error.
#include<stdio.h>

#include<math.h>
long long int sum_of_perfect_divisors(long int);
int main()
{long int i , t,a;
long long int s;




printf("Input the number of test cases \n");
scanf ("%ld",&t);

printf("Enter the values\n");
for(i=0;i<t;i++)
{

scanf("%ld",&a);
printf("\n");
 s= sum_of_perfect_divisors(a);
printf( "%lld\n",s);
}

return 0;
}
 long long int sum_of_perfect_divisors(long int a)
{
long int i,b,finish;    long long s=1;
if(a==1)
return 0;
else if (a==2)
return 1;
else {
finish=sqrt(a);
for(i=2;i<finish;i++)
{
if(a%i==0)
{
s=s+i+a/i;
}
}


if(a%finish==0&& a!=1)
{
long int b=a/finish;
if(finish==b)
s=s+finish;
else
s=s+b+finish;
}
return s;
}
}

[Roshan Singh]

Use cstdio and cmath. I think that should fix it.

--
You received this message because you are subscribed to the Google Groups "Coders in NIT Durgapur" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nitdcoders+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Amisha Bansal]

I tried.  It says wrong answer.  I checked it on ideone,  it's working fine. Idk where the error is.

You received this message because you are subscribed to a topic in the Google Groups "Coders in NIT Durgapur" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/nitdcoders/NzaSnP4jeA0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to nitdcoders+...@googlegroups.com.

[Shailesh Gupta Kool-wal]

Hi,

Its giving wrong output for the number 3.

Regards,

Shailesh Gupta

Mb.No.-+91-8375085502

[Amisha Bansal]

@Shailesh Thanks a ton.  I would try it again with a correct output for 3 then.