## 10394 - Twin Primes

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

Moderator: Board moderators

### 10394 - TLE

here is my code...

Code: Select all
`#include<iostream>#include<stdio.h>#include<vector>#include<math.h>using namespace std;const int MAX=18409202;main(){        vector<bool> primes(MAX,true);        vector<int> pairs;        int i;        primes[0]=primes[1]=false;        /*filter out even nos*/        for(i=4;i<=MAX;i+=2)                primes[i]=false;        /*Sieve method*/        for(i=3;i<=4290;i+=2) {                if(!primes[i])                        continue;                int j;                for(j=i+i;j<=MAX;j+=i)                        primes[j]=false;        }        /*Precompute prime pairs..except (3,5) every other pair of form (6k-1,6k+1) */        int j;        pairs.push_back(3);        for(i=1,j=6;i<100000;j+=6) {                if(primes[j-1] && primes[j+1]) {                        pairs.push_back(j-1);                        i++;                }        }        /*Take input and print*/        int S;        cin >> S;        while(!cin.eof()) {                cout << "(" << pairs[S-1] << ", " << pairs[S-1]+2 << ")\n";                cin >> S;        }}`

Plz tell me hw i can optimize it...
chaos_rulz
New poster

Posts: 2
Joined: Mon Sep 19, 2005 9:17 am

finally got AC
i jst changed it to a C code and made appropriate modifications...
chaos_rulz
New poster

Posts: 2
Joined: Mon Sep 19, 2005 9:17 am

### 10394 , Time limit exceeded

My code is running in 1 sec for 100000, my pc has 256MB of ram.
but giving TLE.please anyone help.
Code: Select all
`#include<stdio.h>#include<math.h>bool pr[20000000]={0};main(){unsigned long count,m,i,n,j,k;double sq;if(19999999%2==0) n=19999999/2-1;/*there are n odd numbers from 3 to 19999999*/else n=19999999/2;sq=floor(sqrt(19999999)+.001);for(i=3;i<=sq;i+=2){   m=i/2-1;if(pr[m]==1) continue;for(j=i;j*i<=19999999;j+=2){ pr[i*j/2-1]=1;}}while(scanf("%lu",&m)!=EOF){count =0;for(i=0;i<n-1;i++){if(pr[i]==0&&pr[i+1]==0) count++;if(count==m) break; }printf("(%lu, %lu)\n",2*i+3,2*i+5);}}`
sobhani
New poster

Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm

### About Time Limit Of Twin_Prime

Your Programm Take time to calulate n'th twin in every input.
try to precaculte all the twin prime before take input.

try with like something this:
Code: Select all
`j=1;for(i=5;i<20000000;i++){  p = i-2;   if( isprime(i)&&isprime(p) )  //make sure that i && p is prime      twin_prime[j++] = p;}while(scanf("%lu",&m)!=EOF)   printf( "(%lu, %lu)\n",twin_prime[m],twin_prime[m]+2 ); `

Rocky
Experienced poster

Posts: 124
Joined: Thu Oct 14, 2004 9:05 am

You can speed it up also by checking numbers next to multiples of 6, since every pair of twin primes is next to multiples of 6.
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### Yehhh.. that's a trick

Thank's
That's a nice trick to speed up solution.

Rocky

Rocky
Experienced poster

Posts: 124
Joined: Thu Oct 14, 2004 9:05 am

Thanks rocky and larry.
I got accepted.
sobhani
New poster

Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm

### 10394 MLE

can anyone help me, how can i save memory?
is it making problem, with my bit operation?
is it wrong way to use bits? plz tell me.
Code: Select all
`/* * 10394 twin primes * submission 0 * coded at 7:51pm, 22th dec 05 * */#include <stdio.h>#include <string.h>#define MAX 20000000/2+1#define MAX_VAL 20000000#define chkbit(num) (status[(num)/2].bit==0)//structure made just for using the bit fiellldsstruct status_type {   unsigned bit :1 ;} status[MAX];long long twinp[100010][2];//the boss!void generate_sieve() {   long long num;   long long temp;      //memset(status, 0, MAX/8);   for(num=3;num<=MAX_VAL;num+=2) {      if (status[num/2].bit==0) {         for(temp=num+num;temp<=MAX_VAL;temp+=num) {            if (temp%2)                status[temp/2].bit= 1;         }      }   }}//main function - what i may not need while i will use the sieveint main() {   long long num;   long long i,j=-1;   generate_sieve();         for(i=5;i<=MAX_VAL,j<100010;i+=2) {      if(chkbit(i) && chkbit(i-2)) {         twinp[++j][1]=i; twinp[j][0]=i-2;      }   }   while(scanf("%lld",&num) ==1)       printf("(%lld, %lld)\n",twinp[num-1][0], twinp[num-1][1]);return 0;}`
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

i found my fault.
thanks->none
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### 10394 Twin Primes TLE

I am using sieve to generate prime numbers and then storing the twin primes. (Pre calculation).
This alone takes something around 10.8 seconds . Please help to make my program run faster. I have done everything i know to optimize my algorithm (at first it took around 15.5 seconds) but now I can't really do anything.
Here's my code:
Code: Select all
`#include<cstdio>#include<iostream>#include<vector>#include<math.h>using namespace std;int main(){        int check[4300]={0},i,j,k,cnt=0,tcnt,primes[800],rt;        vector <int> twins(100000);        for(i=3;i<66;i+=2){                if(check[i]==0){                        k=2*i;                        for(j=i*i;j<4300;j+=k)                                check[j]=1;                }        }        cnt=1;        primes[0]=3;        for(i=5;i<4300;){                if(check[i]==0){                        primes[cnt]=i;                        cnt++;                }                i+=2;                if(i<4300 && check[i]==0){                        primes[cnt]=i;                        cnt++;                }                i+=4;        }        tcnt=2;        twins[0]=3;        twins[1]=5;        k=3;        for(i=11;tcnt<100000;){                if(i%10==3 || i%10==5){                        i+=6;                        continue;                }                cnt=0;                for(j=0;primes[j]<=k;j++){                        if(i%primes[j]==0){                                cnt=1;                                break;                        }                }                if(cnt==1){                        i+=6;                        continue;                }                i+=2;                k=(int)sqrt(i);                cnt=0;                for(j=0;primes[j]<=k;j++){                        if(i%primes[j]==0){                                cnt=1;                                break;                        }                }                if(cnt==1){                        i+=4;                        continue;                }                twins[tcnt]=i-2;                i+=4;                tcnt++;        }        int num;        while(scanf("%d",&num)!=EOF){                printf("(%d, %d)\n",twins[num-1],twins[num-1]+2);        }        return 0;}`
Ankur Jaiswal
New poster

Posts: 31
Joined: Sat Apr 01, 2006 6:24 am

I don't think you read this thread carefully enough:
http://online-judge.uva.es/board/viewto ... ight=10394

And, if you thought you did, why not post in that one, instead making a new thread?

Everything you need is in there.
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

### WHY TLE???????????????

Code: Select all
`code removed`
Last edited by ranban282 on Mon May 22, 2006 9:23 pm, edited 1 time in total.
ranban282
New poster

Posts: 37
Joined: Tue May 02, 2006 1:01 pm

lol...... i modify the code slightly and upload it as c instead of c++ and it gets accepted
ranban282
New poster

Posts: 37
Joined: Tue May 02, 2006 1:01 pm

hi Ankur Jaiswal,
Use this SIEVE code. i think its faster than urs:).

BOOL type use 1 byte
so machine could access memory faster than integer.

Code: Select all
`//Generate prime with Sieve int p[50000];int k;void prime(long MAX){   int i,j;   bool *pr=new bool[50050];   for(i=2;i<=MAX;i++) pr[i]=true;   for(i=2;i<=MAX;i++){      if(!pr[i]) continue;      for(j=i+i;j<=MAX;j+=i){         pr[j]=false;      }   }   k=0;   for(i=2;i<=MAX;i++){      if(pr[i]) p[k++]=i;   }   delete [] pr;}//`
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10394 - Twin Primes why RE?

Here's my code:

C:

#include<stdio.h>
#include<string.h>
char sieve[19999580];
long count=0,twin[100005],i,j;
void main(){
memset(sieve,1,sizeof(sieve));
for(i=4,j=6;i<=19999558||j<=19999558;i+=2,j+=3) sieve[j]=sieve[i]=0;
for(i=5;i<=19999558;i+=2){
if(sieve[i]&&sieve[i-2]) twin[count++]=i-2;
for(j=2*i;j<=19999558;j+=i) sieve[j]=0;
}
while(scanf("%li",&i)!=EOF) printf("%li, %li\n",twin[i-1],twin[i-1]+2);
}

/*end of code*/
Daredevil
New poster

Posts: 19
Joined: Tue Apr 01, 2003 7:47 am
Location: Earth

PreviousNext