10394 - Twin Primes

[chaos_rulz]

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]

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

[adnan2nd]

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

}

}

[Rocky]

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


[Larry]

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.

[Rocky]

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

Rocky

[adnan2nd]

Thanks rocky and larry.
I got accepted.

[smilitude]

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 fielllds
struct 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 sieve
int 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;
}


[smilitude]

i found my fault.
thanks->none

[Ankur Jaiswal]

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


[Darko]

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.

[ranban282]

Code: Select all

code removed


[ranban282]

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

[asif_rahman0]

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


[Daredevil]

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*/