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

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

10394 - TLE

Post by chaos_rulz » Mon Sep 19, 2005 9:20 am

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

Post by chaos_rulz » Mon Sep 19, 2005 10:16 am

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

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

10394 , Time limit exceeded

Post by adnan2nd » Thu Sep 29, 2005 12:19 pm

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

About Time Limit Of Twin_Prime

Post by Rocky » Sun Oct 02, 2005 6:52 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 02, 2005 11:49 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.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Yehhh.. that's a trick

Post by Rocky » Mon Oct 03, 2005 7:25 am

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

Rocky

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by adnan2nd » Thu Oct 06, 2005 3:42 pm

Thanks rocky and larry.
I got accepted.
sobhani

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10394 MLE

Post by smilitude » Thu Dec 22, 2005 5:09 pm

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;
}
fahim
#include <smile.h>

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jan 12, 2006 8:31 pm

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

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

10394 Twin Primes TLE

Post by Ankur Jaiswal » Fri May 19, 2006 5:43 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri May 19, 2006 5:59 pm

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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

WHY TLE???????????????

Post by ranban282 » Mon May 22, 2006 3:05 am

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

Post by ranban282 » Mon May 22, 2006 3:28 am

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

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

Post by asif_rahman0 » Sun Jun 11, 2006 6:15 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;
}
//

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

10394 - Twin Primes why RE?

Post by Daredevil » Sun Jul 02, 2006 1:38 pm

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=0;
for(i=5;i<=19999558;i+=2){
if(sieve&&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*/

Post Reply

Return to “Volume 103 (10300-10399)”