## 10394 - Twin Primes

Moderator: Board moderators

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

### 10394...memory limit Exceed

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
Contact:
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
thnx my friend   i gor AC

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

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;
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
Contact:

### run time error

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

Code: Select all

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

long int ar,t,t1 ;
char   arr;

void get_prime(long int n)

{

long int x ;
//char   arr;
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

### Re: 10394 - Twin Primes

Some body help me. I am getting RTE.. 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
Contact:

### Re: 10394 - Twin Primes

Code: Select all

``gprime[j] = 1; // for(j = i * i; j <= 20000000;j+=i) so j can be 20000000, but you declared gprime``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10394 - Twin Primes

But this Passed time limit!!! What is the reason for it??? I used faster method for generating primes. 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

### Re: 10394 - Twin Primes

Thank you all. That was a bad mistake. 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

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;
void seive()
{
int m=4290;
memset(prime,true,sizeof(prime));
prime=false;
prime=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
Contact:

### Re: 10394 - Twin Primes

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

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
Contact:

### Re: 10394 - Twin Primes

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, a maps to 0 to 31, a 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

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

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,c,flag,b;

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;
a=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]=a[i-1];
b[j]=a[i];
j++;
}
if(j==n)
break;
}
printf("(%lld, %lld)\n",b[j-1],b[j-1]);
}
return 0;
}
``````