## 10394 - Twin Primes

Moderator: Board moderators

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

### 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=primes=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...

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

### 10394 , Time limit exceeded

My code is running in 1 sec for 100000, my pc has 256MB of ram.

Code: Select all

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

bool pr={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

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

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### Yehhh.. that's a trick

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

Rocky

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:
Thanks rocky and larry.
I got accepted.
sobhani

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

### 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 fielllds
struct status_type {
unsigned bit :1 ;
} status[MAX];

long long twinp;

//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]=i; twinp[j]=i-2;
}
}

while(scanf("%lld",&num) ==1)
printf("(%lld, %lld)\n",twinp[num-1], twinp[num-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>

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

### 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={0},i,j,k,cnt=0,tcnt,primes,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=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=3;
twins=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
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???????????????

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:
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
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;
int k;
void prime(long MAX)
{
int i,j;
bool *pr=new bool;
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?

Here's my code:

C:

#include<stdio.h>
#include<string.h>
char sieve;
long count=0,twin,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*/