10394 - Twin Primes

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

Moderator: Board moderators

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

10394...memory limit Exceed

Post by Iffat » Mon Aug 28, 2006 7:50 pm

i got memory limit Exceed....

Code: Select all

CUT
plzz help me :(
thanx
Last edited by Iffat on Tue Aug 29, 2006 2:25 pm, edited 1 time in total.

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi » Mon Aug 28, 2006 9:13 pm

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.
Sanjana

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Post by Iffat » Tue Aug 29, 2006 2:21 pm

thnx my friend :) :) :)
i gor AC

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita » Fri Sep 08, 2006 8:00 am

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............
win

dipaly
New poster
Posts: 20
Joined: Tue Sep 19, 2006 6:18 pm
Location: bangladesh
Contact:

run time error

Post by dipaly » Thu Aug 09, 2007 4:36 pm

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
everything is so hard to me

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

Re: 10394 - Twin Primes

Post by Obaida » Thu May 15, 2008 1:44 pm

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

Code: Select all

Removed
Last edited by Obaida on Sun May 18, 2008 11:19 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10394 - Twin Primes

Post by Jan » Thu May 15, 2008 2:28 pm

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.
Ami ekhono shopno dekhi...
HomePage

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

Re: 10394 - Twin Primes

Post by Obaida » Sat May 17, 2008 7:18 am

But this Passed time limit!!! :o
What is the reason for it??? I used faster method for generating primes. :o
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

Re: 10394 - Twin Primes

Post by Obaida » Sun May 18, 2008 11:20 am

Thank you all. That was a bad mistake. :oops:

Code: Select all

I get Accepted
try_try_try_try_&&&_try@try.com
This may be the address of success.

shekhar
New poster
Posts: 6
Joined: Wed Jul 09, 2008 12:34 pm

Re: 10394 - Twin Primes

Post by shekhar » Sun Jul 13, 2008 1:53 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10394 - Twin Primes

Post by Jan » Sun Jul 13, 2008 5:11 pm

Use bitwise sieve and don't use 'system("pause");'.
Ami ekhono shopno dekhi...
HomePage

shekhar
New poster
Posts: 6
Joined: Wed Jul 09, 2008 12:34 pm

Re: 10394 - Twin Primes

Post by shekhar » Tue Jul 15, 2008 3:25 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10394 - Twin Primes

Post by Jan » Tue Jul 15, 2008 9:12 pm

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.
Ami ekhono shopno dekhi...
HomePage

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Re: 10394 - Twin Primes

Post by rhsumon » Fri Aug 22, 2008 12:02 am

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
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

Re: 10394 - Twin Primes

Post by fahmi » Sat Jan 10, 2009 6:24 pm

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;
}

Post Reply

Return to “Volume 103 (10300-10399)”