10394 - Twin Primes

[Iffat]

i got memory limit Exceed....

Code: Select all

CUT

plzz help me
thanx

[kolpobilashi]

Dear Iffat
you used 2 big size long long array,which certainly caused MLE.here the thing you can do,
1. for prime generating use seive algo with a bool array of max 20000000 size.by taking bool type array you can save enough memory.
2.you can then take your 2nd array to store the twin primes of long type(no need for long long) and for this the size 100000 is enough.
hope u'll get AC soon.

[Iffat]

thnx my friend
i gor AC

[vinit_iiita]

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int l=1,u=20000000,d,j;
    
    
    d=u-l+1;
    bool *flag=new bool[d];
    for (int i=0;i<d;i++)
    flag[i]=true;
    for (int i=(l%2!=0);i<d;i+=2)
    flag[i]=false;
    for (int i=3;i<=sqrt(u);i+=2)
    {
        j=l;
        while (j%i!=0)
        j++;
        for (j=j+i;j<u;j+=i)
        flag[j-l]=false;
        }
               
  if (l<=1) flag[1-l]=false;
  if (l<=2) flag[2-l]=true;

  
  int c=1;
  int b[110002];
  for (int i=0;i<d;i++) if (flag[i] && flag[i+2]) 
  {
    
       b[c-1]=i+l;
      
      
      c++; 
     
  }
  
 int n;               
 while (cin>>n)
 {
     
            int t=b[n-1];
            cout<<"("<<t<<", "<<t+2<<")"<<endl;
 }
return 0;
}

friends i got AC but it's too slow 9.57 s and memory used is also high 1900
plz suggest ways to better it............

[dipaly]

my this code gets run time error .. but why?

Code: Select all

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



long int ar[100005],t,t1 ;
char   arr[200000005];

void get_prime(long int n)

{

	long int x ;
	//char   arr[20000005];
	long int k=1,l;

	for (x =1 ; x <= n ; x++)
	{
		arr[x]='0';
	}

	while( k <= sqrt(n))
	{
		if(arr[k] == '1' ||k==1)
		k++;

		else 
		{
			for(int i=2 ; l<=n ;i++ )
			{
				l=i*k;
				arr[l] = '1';

			}
			l =0;
			k++;
		}
	}
	
	t=0;
	t1=0;
	for(k=3 ;k <=n; k++)
	{
	   if(arr[k]!='1' &&((arr[k+2] != '1') || (arr[k-2] != '1')))
	   {
			  ar[t1] = k;
			  t1++;
	   }
	}

}



int main()
{ 
	get_prime(20000000);

	long int n;
	while(scanf("%ld",&n)==1)
	{
		printf("(%ld, %ld)\n",ar[n-1],ar[n]);
	}
	return 0;
}

thanks

[Obaida]

Some body help me. I am getting RTE..
What's the problem!!!

Code: Select all

Removed

[Jan]

Code: Select all

gprime[j] = 1; // for(j = i * i; j <= 20000000;j+=i) so j can be 20000000, but you declared gprime[1000000]

Hope it helps.

[Obaida]

But this Passed time limit!!!
What is the reason for it??? I used faster method for generating primes.

[Obaida]

Thank you all. That was a bad mistake.

Code: Select all

I get Accepted

[shekhar]

Hi!! everyone...
I am fed up with this question...
changed my sieve method lot of time.
my present sieve method takes around 1.1-1.2 seconds.I also used the concept of twin primes around multiples of 6...
then also getting TLE...
PLZ Help..here is my code...

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
bool prime[18409202];
void seive()
{
     int m=4290;
     memset(prime,true,sizeof(prime));
     prime[0]=false;
     prime[1]=false;
     for(int i=2;i<=m;i++)
     if(prime[i]) for(int k=i*i;k<=18409202;k+=i)
                  prime[k]=false;
}
int main()
{
    
    seive();
    long i,count,s;
    while(cin>>s) 
    {
                 if(s==1)
                 cout<<"(3, 5)"<<endl;
                 else if(s>1)
                 {
                         count=1;i=5;
                         while(count!=s)
                         {
                                        if(prime[i] && prime[i+2])
                                        count++;
                                        i=i+6;
                         }
                        cout<<"("<<i-6<<", "<<i-4<<")"<<endl;
                 }
    }
    system("pause");
    } 

[Jan]

Use bitwise sieve and don't use 'system("pause");'.

[shekhar]

Thanks Jan for your reply.
As far as system("pause") is concerned,it does not make any kind of problem.
I have submitted many problems in UVa with system("pause").
or Does using system("pause") increases runtime??
Plz Can u explain how Bit-wise sieve is done?

[Jan]

I haven't find any reason to use 'system("pause")'. However, its up to you. About bitwise sieve, bool takes 8 bits. So, when you assign something in prime, it will change all the 8 bits. You can use integer array, and imagine that each bit of the array maps an integer. Say a[2], a[0] maps to 0 to 31, a[1] maps to 32 to 63 (cause an integer has 32 bits). Now you can use bitwise operations to use the array.

Also, you can try google. Hope these help.

[rhsumon]

would u plz someone look at my code
why it gives RTE............
here is my code:

Code: Select all

At Last AC in 1.4 sec

plz help someone

[fahmi]

my code doesnt work for 100000.what can i do now?? plz som1 help

Code: Select all

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

long long a[100000],c,flag[1000000],b[10000][100];

void seive(long long n)
{
	long long k,i,j,r;
	k=sqrt(n);
	for(i=1;i<=n;i++)
		flag[i]=0;
	flag[1]=1;
	a[0]=2;
	c=1;
	for(i=4;i<=n;i+=2)
		flag[i]=1;
	for(i=3;i<=n;i+=2)
	{
		if(flag[i]==0)
		{
			a[c++]=i;
			if(k>=i)
			{
				r=i+i;
				for(j=i*i;j<=n;j+=r)
					flag[j]=1;
			}
		}
	}
	a[c]=0;
}

int main()
{ 
	long long n,f,i,p,j;
	seive(2000000);
	while(scanf("%lld",&n)==1&&n>0)
	{
		f=0;
		j=0;
		for(i=1;i<c;i++)
		{
			if(a[i]-2==a[i-1])
			{
				b[j][0]=a[i-1];
				b[j][1]=a[i];
				j++;
			}
			if(j==n)
				break;
		}
		printf("(%lld, %lld)\n",b[j-1][0],b[j-1][1]);
	}
	return 0;
}