10200 - Prime Time

[anupam]

i can't find a better way to solve it, it got tletle...
will anyone help please

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 10100
main()
{
	long k=0,i,j,l,z,a[N],r,m,n,val;
	for(i=2;i<=10100;i++)
	{
		for(j=2;j<=(i/2);j++)
			if(!(i%j))
				break;
		if(j>(i/2)) a[k++]=i;
	}
	while(1)
	{
		r=scanf("%ld%ld",&m,&n);
		if(r==EOF) break;
		z=0;
		for(i=m;i<=n;i++)
		{
			val=(i*i)+i+41;
			l=0;
			for(j=0;a[j]<=sqrt(val);j++)
				if(!(val%a[j]))
				{
					l=1;
					break;
				}
			if(!l) z++;
		}
		printf("%.2lf\n",z*100.00/(double)(n-m+1));
	}
	return 0;
} :oops:  :oops: 

[anupam]

please check the source code
it gets tle again

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 10100
main()
{
	long k=0,i,j,l,z,a[N],r,m,n,val;
	for(i=2;i<=10100;i++)
	{
		for(j=2;j<=(i/2);j++)
			if(!(i%j))
				break;
		if(j>(i/2)) a[k++]=i;
	}
	while(1)
	{
		r=scanf("%ld%ld",&m,&n);
		if(r==EOF) break;
		z=0;
		for(i=m;i<=n;i++)
		{
			val=(i*i)+i+41;
			l=0;
			for(j=0;a[j]<=sqrt(val);j++)
				if(!(val%a[j]))
				{
					l=1;
					break;
				}
			if(!l) z++;
		}
		printf("%.2lf\n",z*100.00/(double)(n-m+1));
	}
	return 0;
}

please help me

[Larry]

[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int isp( int x ){
int i;
if ( x % 2 == 0 ) return 0;
for ( i = 3; i * i <= x; i += 2 )
if ( x % i == 0 ) return 0;
return 1;
}

int main(){
char c[10005];
int i;
int d, a, b;

for ( i = 0; i <= 10005; i++ ){
d = ( i * i ) + i + 41;
c = isp( d );
}

while ( 2 == scanf("%d %d", &a, &b ) ){
d = 0;
for ( i = a; i <= b; i++ )
d += c;
printf("%.2lf\n", ( (double) d ) / ((double) ( b - a ) + 1 ) * 100.0 );
}
}
[/c]

This is a pretty slow way, but it works within the time..

[Eric]

In fact, before any input is read, you should think about a thing.
If case 1 is the interval 39 to 400 and the case 2 is the 39 to 400 again, you will run two times for the answer.
So make sure you can tackle the problem.

[anupam]

thank u liu and larry for your advices. i am now careful abuot such simple mistakes in algthms.
thanks again. [/b]

[Giggs]

int ifprime(int n)
{int j;
for(j=2;j<n;j++)
{if (n%j!=0) continue;
else return (0);}
if(n==j)
return (1);
}

int creat_num(int n)
{int m;
m=n*n + n + 41;
return m;
}

main()
{int a,b,i;
float pre,sum;
int re=0;
clrscr();
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++)
re=re+ifprime(creat_num(i));
sum=(float) re;
pre=sum*100/(b-a+1);

printf("%5.2f",pre);
}

[Giggs]

i don't konw how to submit that,so i paste it hehe

[Giggs]

int ifprime(int n)
{int j;
for(j=2;j<n;j++)
{if (n%j!=0) continue;
else return (0);}
if(n==j)
return (1);
}

int creat_num(int n)
{int m;
m=n*n + n + 41;
return m;
}

main()
{int a,b,i;
float pre,sum;
int re=0;
clrscr();
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++)
re=re+ifprime(creat_num(i));
sum=(float) re;
pre=sum*100/(b-a+1);

printf("%5.2f",pre);
}

[anupam]

it gets wa.
so how it works?
format your code please.
it is hard to understand.

[Giggs]

i can't get yours points. yours progremm and mine are both ok, i can run them on my computer.

int ifprime(int n) /*justify whether it is a prime*/
{int j;
for(j=2;j<n;j++)
{if (n%j!=0) continue;
else return (0);}
if(n==j)
return (1);
}

int creat_num(int n)
{int m;
m=n*n + n + 41;
return m; /*creat a new number with Euler formule by the given number */
}

main()
{int a,b,i;
float pre,sum;
int re=0;
clrscr();
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++)
re=re+ifprime(creat_num(i)); /*creat a number, justify whether it is a prime and then if it is then retuen a "1" ,or a 0" */


sum=(float) re;
pre=sum*100/(b-a+1);

printf("%5.2f",pre);
}

[Riyad]

i am having trouble with 10200 . having TLE all the time. plizzzzz help
here is my code:

Code: Select all

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

#define size 500000

int prime[size];
int prime_no=2;

void init(){
	
	register long int i ;
	
	prime[0]=1;
	prime[1]=2;
	
	for(i =2;i<size;i++){
		prime[i]=0;

	}

}

void prime_gen(long int n ){

	register int flag;
	register long int i,j;
	flag=0;

	init();

	for(i=3;i<=n;i+=2){
		for(j=1;j<prime_no && !flag; j++){

			if((i%prime[j])==0){

				flag=1;
			}
			else
				continue;
		}

		if(flag==0){

			prime[prime_no++]=i;
		}

		flag=0;
	}
}




int check(long int c){
	register int low,high,mid;
	low=0;
	high=prime_no -1;
	while(low<=high){
	
		mid=(low+high)/2;

		if(c<prime[mid])
			high=mid-1;
		else if(c> prime[mid])
			low=mid+1;
		else
			return 1;
	
	
	
	}
	return 0;


}


void calculate( int e, int l){

	register int i,total;
	long int temp;
	int count=0;
	double result,t1,t2;
	int flag=0;
	total=l-e+1;
	

	for(i=e;i<=l;i++){
	
		temp=i*i + i + 41;
		flag=check(temp);
		if(flag==1){
		
			count++;
			
		}
		else
			continue;
		flag=0;
	
	}
	

	t1=count;
	t2=total;
	result=(t1/t2)*100;
	
	printf("result is %0.2lf\n",result);
	




}






int main(){

	int e,l;
	

	prime_gen(100010041);

	while(scanf("%d %d",&e,&l)==2){
		
		calculate(e,l);
		
	
	
	}
	
	return 0;
}

thanx in advance
Bye
Riyad

[shamim]

Well I compiled ur code using cygwin and it does not even allow me to take any input. It is obvious that it should receive time limit.

I think the program gets stuck in the prime_gen(100010041); part.

[Riyad]

i haven't got any algorithm for genarating prime number fast . My way of generating prime is obviously very slow. i have got two code of generating prime from the board but cant use it properly as i am a new person here in acm . so it will be a great help if u can tell me how to use that two algorithms.Bye
Riyad

Code: Select all

#include<stdlib.h>
#include<malloc.h>

#define isprime(f,x) (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define setprime(f,x) *(f+(x)/16)|=1<<(((x)%16L)/2)

void main()
{
unsigned char *field=NULL,*zzz;
unsigned long teste=1,max,mom,count,alloc;
int d;
max=20010000L;

while(field==NULL)
zzz=field=(unsigned char*) malloc(alloc=(((max-=10000L)>>4)+1L));

for (count=0;count<alloc;count++)
*zzz++ = 0x00;

while((teste+=2)<max)
if(!isprime(field,teste))
for(mom=3L*teste;mom<max;mom+=teste<<1)
setprime(field,mom);
	if(isprime(field,3)==1)
/*now you can call the module isprime to check any positive integer 
either prime or not; 
syntax: 
isprime(field,integer); 

if the module return 0 the integer will be prime 
else not prime. 

you can check upto 20000000 within a while 
*/ 

free (field); 
}

/* ***********************************************/
MY QUESTION----->
/*what should i use in place of the parameter "field" in the function 
isPrime(field , integer). that means what should i do if i want to check the primality of the number 100010041.*/ 

/*********************************************/






/**********************SIEVE********************************/



#define MAXSIEVE 100000000 // All prime numbers up to this 
#define MAXSIEVEHALF (MAXSIEVE/2) 
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2 
char a[MAXSIEVE/16+2]; 
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd 

int i,j; 
memset(a,255,sizeof(a)); 
a[0]=0xFE; 
for(i=1;i<MAXSQRT;i++) 
if (a[i>>3]&(1<<(i&7))) 
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1) 
a[j>>3]&=~(1<<(j&7)); 

Sorry for my being too stupid to paste a code that i even dont understand

[Riyad]

i am having tle in the program 10200 . is there any faster algo than mine . here is my code . pliiiiiiiiiiiiizzzzzzzzzzzzz help

Code: Select all

#include<stdio.h>

#include<math.h>


int isPrime(long int x){

	register long int i ;
	
	for(i=2;i<=sqrt(x);i++){
	
		if((x%i)==0){
			
			return 0;
		}
		else
			
			continue;
	}
	return 1;


}


void calculate(int a , int b){


	register  int i,check;
	long int temp;
	double count=0;
	double total;
	
	
	total=b-a+1;
	
	for(i=a;i<=b;i++){
	
		temp=i*i + i + 41;
		
			
		check=isPrime(temp);
		if(check==1){
			count++;
		}
		else
			continue;
		
	
	}
	count=(count/total)*100;
	printf("%.2lf\n",count);



}


int main(){

	int a,b;
	
	
	while(scanf("%d %d",&a,&b)==2){
	
		calculate(a,b);
	
	}
	
	
	return 0;
}

Waiting for u r help
Bye
Riyad

[shamim]

The way you generate the primes is too costly wiht respect to time.
One method is to use existing primes to find new primes.
here is the algorithm.

[cpp]
primes[MAX];

genprime()
{
prime[0]=2; prime[1]=3;prime[2]=5;prime[3]=7;
count=4;
long int num,i;
for(num=11;num<MAX;num=num+2)
{
for(j=0;j<count;j++)// can be made faster if j<sqrt(prime[count-1] is used
if(num%prime[j]==0) break;
if(j==count)
prime[count++]=num;
}
}
[/cpp]