10200 - Prime Time

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

Moderator: Board moderators

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10200 - Prime Time

Post by vahid sanei » Tue Feb 10, 2009 9:25 am

THANKS Jan
it works with eps :D
Impossible says I`m possible

Shreif
New poster
Posts: 2
Joined: Mon Mar 16, 2009 1:29 am

Re: 10200 - Prime Time

Post by Shreif » Mon Mar 16, 2009 1:39 am

i'm getting WA and don't know why
plz help
here is my code

Code: Select all

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

bool prime[10000]={0};

bool isprime(long long x)
{
	int end=sqrt(double(x))+1;
	for(int q=3;q<=end;q+=2)
				if(x%q==0)
					return false;
	return true;
}

void getprimes()
{
	int limit = 10000, i, j;
	for(i=40; i<=limit; i++)
	{
		long long temp=(i)*(i);
		temp+=(i);
		temp+=41;
		if(isprime(temp))
			prime[i]=1;
	}
}

int main()
{
	getprimes();
	int a=0,b=0;
	while(cin>>a>>b)
	{
		if(b<40)
			cout << "100.00\n";
		else
		{
			float tot = b-a+1;
			float count=0;
			for(int z=a;z<=b;z++)
			{
				if(z<40)
				{
					int o=40-z;
					count+=o;
					z=40;
				}
				if(prime[z]==1)
					count++;
			}
			float per = count/tot;
			per=per*100;
			cout << fixed;
			cout << setprecision (2) << per << endl;
		}
	}
	return 0;
}

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10200 - Prime Time

Post by vahid sanei » Mon Mar 16, 2009 7:16 am

you should use

Code: Select all

double per 
instead of

Code: Select all

float per
and change this

Code: Select all

int end=sqrt(double(x))+1;
to

Code: Select all

int end=sqrt(double(x));
use eps for your ans

Code: Select all

#define eps 1e-9
cout << setprecision (2) << per + eps << endl;
Impossible says I`m possible

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10200 - Prime Time

Post by vahid sanei » Mon Mar 16, 2009 7:16 am

----
Last edited by vahid sanei on Mon Mar 16, 2009 12:26 pm, edited 1 time in total.
Impossible says I`m possible

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10200 - Prime Time

Post by vahid sanei » Mon Mar 16, 2009 7:16 am

----
Last edited by vahid sanei on Mon Mar 16, 2009 12:24 pm, edited 1 time in total.
Impossible says I`m possible

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10200 - Prime Time

Post by Obaida » Mon Mar 16, 2009 7:53 am

To vahid..
You should clean up al these extra post. :oops:
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10200 - Prime Time

Post by vahid sanei » Mon Mar 16, 2009 8:39 am

i dont know Why i cant clean those posts , my connection have some problem , and web site resent twice my post
just i have edit , report and quota options :(
Impossible says I`m possible

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10200 - Prime Time

Post by Obaida » Mon Mar 16, 2009 9:23 am

Then 1 thing you can do.
Go to edit and erase the wring of extra posts. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

Shreif
New poster
Posts: 2
Joined: Mon Mar 16, 2009 1:29 am

Re: 10200 - Prime Time

Post by Shreif » Mon Mar 16, 2009 5:06 pm

thnx vahid sanei i got AC
plz anyone knows what is the eps tell me or post me a link to read about it
thnx all

Landadel
New poster
Posts: 1
Joined: Mon Mar 16, 2009 8:52 pm

Re: 10200 - Prime Time

Post by Landadel » Mon Mar 16, 2009 9:22 pm

Hello everyone,

I am new to ACM and Online-Judge. I wanted to try out how everything works with this problem. Unfortunatly I always get a time limit exceeding. I think it has to do with the end of line of the standard in. Can someone please help me, so I can get started here?

Code: Select all

import java.io.*;
import java.util.StringTokenizer;

public class Main {	
	
	public static boolean isPrime(int num){
		
		double testPrime = Math.sqrt(num);
		
		if (num==0 || num==1 || num==2)
			return false;
		
		for (int i=3;i <= testPrime;i+=2){
			if (num%i==0)
				return false;
		}
		
		return true;
		
	}	
	
	public static void main(String[] args) throws Exception
	{
		 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	     String line = "";
		 StringTokenizer data;
	     int start, end, counter, interval;
	     double percentage;
	     
	     while ((line = reader.readLine()) != null) 
	     {
	          counter = 0; 
	    	  data = new StringTokenizer(line);
	    	  
	          start = Integer.parseInt(data.nextToken());
	          end = Integer.parseInt(data.nextToken());
	          interval = end - start + 1;
	          
	          for(int i=start; i<=end; i++)
	          {
	        	  if(isPrime(i*i+i+41))
	        		  counter++;
	          }
	          
	          percentage = ((double)counter)/interval*100;
	          percentage = Math.round(percentage*100)/(double)100;
	          
	          System.out.println(percentage);	         
	     }	
	}
}
Thanks for any help!
Best regards, Landadel

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Location: CUET, Chittagong, Bangladesh
Contact:

Re: 10200 - Prime Time

Post by aliahmed » Thu Jul 09, 2009 9:19 am

Thanks mf.

Accepted after using eps
Last edited by aliahmed on Thu Jul 09, 2009 8:03 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10200 - Prime Time

Post by mf » Thu Jul 09, 2009 1:19 pm

Because double's are no good in this problem, and you can't read the last few pages of this thread!

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10200 - Prime Time

Post by asif_khan_ak_07 » Fri Oct 23, 2009 8:15 am

I am getting WA from the judge..all the test cases given in this forum matches with my output..please point out the mistake.

Code: Select all

#include<stdio.h>
#include<math.h>
#define MAX 1000000
bool pr[MAX];
int pri[80000];
void sieve(){
	int ns=0;
	int sq;
	sq=sqrt(MAX);
	pr[0]=true;
	pr[1]=true;
	pri[ns++]=2;
	for(int i=4;i<=MAX;i+=2)
		pr[i]=true;
	for(int j=3;j<=MAX;j++){
		if(pr[j]==false)
			pri[ns++]=j;
		if(j<=sq){
			for(int k=j*j;k<=MAX;k+=(2*j))
				pr[k]=true;
		}
	}

	//printf("%d",ns);

}


int main(){
//	freopen("10220.txt","r",stdin);
	int n,m,prime,count,ns,sq,fg;
	double ans;
	sieve();
	while((scanf("%d %d",&n,&m)==2)){
	count=0;
	for(int i=n;i<=m;i++){
		prime=(i*i)+i+41;
	//	printf("%d ",prime);
	
	if(prime<=1000000){
		if(pr[prime]==false)
			count++;
		}
	
	else {
		sq=sqrt(prime);
		fg=0;
		for(int j=0;pri[j]<=sq;j++){
			if(prime%pri[j]==0){
				fg=1;
				break;
			}
		}
	
		if(fg==0)
			count++;
	}
	
	}
	ns=m-n+1;
	ans=count/(double)(ns);
	ans*=100;
	
	printf("%.2lf\n",ans);

	}

return 0;
}

sudipta
New poster
Posts: 11
Joined: Wed Sep 30, 2009 7:23 pm
Location: Sylhet

10200 Prime Time

Post by sudipta » Thu Nov 05, 2009 6:46 pm

What is wrong?

Code: Select all

#include<stdio.h>
#include<math.h>
#define len 10000000
char prime[len+1];
void sieve()
{
    int i,j,k=0,r;
    prime[0]=prime[1]=0;
    prime[2]=1;
    for(i=3;i<=len;i+=2)
    {
        prime[i]=1;
        prime[i+1]=0;
    }
    r=(int)sqrt(len);
    for(i=3;i<=r;i++)
    {
        if(prime[i]==1)
        {
            for(j=i*i;j<=len;j+=i*2)
            {
                prime[j]=0;
            }
        }
    }

}

int main()
{
    sieve();
    int n1,n2,t,i,j,n;
    float per,d,p;
    while(scanf("%d%d",&n1,&n2)==2)
    {
        p=0;
        if(n1>n2)
        {
            t=n1;
            n1=n2;
            n2=t;
        }
        d=n2-n1+1;
        for(i=n1;i<=n2;i++)
        {
            n=i*i+i+41;
            if(prime[n]==1) p++;
        }
        per=(p/d)*100;
        printf("%.2f\n",per);
    }
    return 0;
}
Don't Copy, Think Also

masum.shafayat
New poster
Posts: 3
Joined: Wed Nov 11, 2009 1:09 pm

Re: 10200 Prime Time

Post by masum.shafayat » Wed Nov 18, 2009 12:58 pm

Code: Select all

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	bool prime[10005];
	int p=0;
	prime[0]=false;
	prime[1]=false;
	for(p=2;p<=10000;p++)
		prime[p]=true;
	int i;
	for(p=2;p<10001;p++)
	{
		for(i=p*2;i<=10000;i=i+p)
		{
			if(prime[i])
			{
				prime[i]=false;
			}
		}
	}
	bool rp[10005];
	for(i=0;i<=10000;i++)
		rp[i]=true;
	for(i=2;i<=10000;i++)
	{
		int g=0,res;
			res=i*i+i+41;

				for(g=2;g<=sqrt(res);g++)
				{
					if(res%g==0&&prime[g])
					{
						rp[i]=false;
						break;
					}
				}
	}

	int a,b;
	while((scanf("%d%d",&a,&b))==2)
	{
		int c=0,pc=0;
		for(c=a;c<=b;c++)
		{
			pc=pc+rp[c];
		}
		float avg=(float)((pc*100))/(float)((b-a+1));
		printf("%.2f\n",avg);
	}

	return 0;
}
What wrong here???????
anybody help me please???????

Post Reply

Return to “Volume 102 (10200-10299)”