10200 - Prime Time

[helloneo]

Read the previous posts.. (about EPS)

[ankit.arora]

I m gettin WA but i have checked my output for all inputs provided in this thread!..... Please help me!!!

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    unsigned long long i,j,count,t;
    int set;
    int arr[100001]={0};
    arr[0]=1;
    arr[1]=1;
    for(i=2;i<100001;i++)
    {
           if(arr[i]==0)
           {
                   j=2;     
                   while(i*j<100001)
                   {
                           arr[i*j]=1;
                           j++;
                   }
           }
    }
    
    unsigned long long num[10001];
    count=0;
    for(i=0;i<=10000;i++)
    {
           t=(i*i)+i+41;
           if(t<=100000)
           {
                   if(arr[t]==0)     
                   count++;
                   num[i]=count;
           }
           
           else
           {
                   set=0;
                   for(j=3;j<=sqrt((double)t+0.5);j+=2)
                   {
                          if(t%j==0)
                          {
                                 set=1;
                                 break;
                          }
                   }
                   
                   if(set==0)
                   count++;
                   num[i]=count;
           }
    }
    
    int a,b;
    double per;

    while(cin>>a>>b)
    {
           if(a==0)         
           per=100*((double)(num[b])/(double)(b-a+1));
           else
           per=100*((double)(num[b]-num[a-1])/(double)(b-a+1));
           
           t=(long long)(per*100);
           if((per*100)-t>0.5 ||((per*100)-t==0.5 && t%2!=0))
           t++;
           
           if(t%100==0)
           cout<<(double)t/(double)100<<".00\n";
           else if(t%10==0)
           cout<<(double)t/(double)100<<"0\n";
           else
           cout<<(double)t/(double)100<<"\n";
    }         
}                                                                         

[mmonish]

>>ankit.arora
did u check the sample inputs. for the following input 1423 2222 ur output is 44.12 but the correct output is 44.13.
use double calculation and output like this
printf(".2lf\n" , res);
and don't forget about EPS.

Hope this helps.

[ankit.arora]

>>ankit.arora
did u check the sample inputs. for the following input 1423 2222 ur output is 44.12 but the correct output is 44.13.
use double calculation and output like this
printf(".2lf\n" , res);
and don't forget about EPS.

Hope this helps.

Actually for this input the actual floating answer is 44.125(as per my program) which when rounded to two decimal places produces 44.12, this is the rule which i use in all my rounding calculations ..... can you please explain me that why it should be 44.13 instead.

Thanks a lot for helping!!!!

[shaiful]

I got 20 WA in this problem
Can any one help me on my code?

Code: Select all

#include<stdio.h>
#include<math.h>


bool prime(long long n)
{
       long long i,sq;
       sq=(long long)sqrt((double)n);

       for(i=2;i<=sq;i++)
       {
               if(n%i==0) return false;
       }
       return true;
}

int main()
{

       long long dif,count,temp,t,i,j,n1,n2,k;

       bool p[10005];

       for(j=0;j<10005;j++) p[j]=false;
       for(j=0;j<10005;j++)
       {
               temp=j;
               k=temp*temp+temp+41;
               if(prime(k)==true)
                       p[j]=true;
       }
       double per;

       while(scanf("%lld %lld",&n1,&n2)==2)
       {
               count=0;
               if(n1>n2)
               {
                       t=n1;
                       n1=n2;
                       n2=t;
               }

               for(i=n1;i<=n2;i++)
               {
                       if(p[i]==true) count++;
               }
               dif=n2-n1+1;
               per=(double)((double)count/(double)dif)*100.0;

               printf("%.2lf\n",per);
       }
       return 0;
}

[emotional blind]

This problem can be solved without using float or double..
That will be more safe.

[WingletE]

I've passed all the test case above but still got WA, I use long double.
What could the problem be?

This problem can be solved without using float or double..

then how?

[mf]

You could round and output a fraction p/q, for example with this code:

Code: Select all

int t = (p * 200 + q) / (2 * q);
printf("%d.%.2d\n", t / 100, t % 100);

[ishtiaq ahmed]

Code: Select all

cut after AC

[WingletE]

I've run your program. Your answer is not right.

Code: Select all

9999 10000
9998 10000
9998 9999
9996 10000
500 600

Code: Select all

0.00
0.00
0.00
20.00
56.44

[ishtiaq ahmed]

i rewrite my code as follows but stll facing WA.

Code: Select all

cut after AC

waiting for your reply

[Fuad Hassan EWU]

WA!!! i can't find the bug. i used very simple and i think simple logic coz this seems to be eay problem. but where is the bug? I matched the provided critical input output. plz help...

Code: Select all

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define N 120000000

using namespace std;


char a[N/2+10];

void genprime()
{

	long i,j;

	for(i=3;i*i<=N;i+=2)
	{
		if(a[i/2]==1)
			continue;
		for(j=(i*i)/2;j<=N/2;j+=i)
		{
			a[j]=1;
		}
	}

	

}




int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	genprime();
	double prmcnt;
	double result;
	long i,first,b, f;
	while(cin>>first>>b)
	{
	
	prmcnt=0;
	

		for(i=first;i<=b;i++)
		{
		

			f=(i*i)+i+41;

			if(f==2)
				prmcnt++;

			else if(f%2==0&&f!=2)
				continue;

			else
			{
				if(a[f/2]==0)
					prmcnt++;
				else
					continue;
			}
		}


		result=(100*(double)prmcnt)/(double)((b-first)+1);
		printf("%.2lf\n",result);


	}
	
	
	return 0;
}

[Jan]

Your code is taking too much memory.

[Fuad Hassan EWU]

jan vai i used the size 100010041, because 10000^10000+10000+41=100010041. and to check whether it is prime or not i need to run a the outer of my seive method up to sqrt(100010041). am i right? plz make me clear about this issue. thanks.

[Jan]

int (sqrt(100010041)) = 10000. There are less than 2460 primes in [2,10000]. So, in worst case you have to divide 2460 times to check whether a number is prime or not. And this isn't too much. It uses less memory, but takes a little more time. So, you can generate primes upto 10000, and make your primarity testing. Hope it helps.