## 10394 - Twin Primes

Moderator: Board moderators

fahmi
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

### Re: 10394 - Twin Primes

using i+=6,my code is..but still big numbers cannot b executed

Code: Select all

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

long long a[100000],c,flag[1000000],b[10000][10000];

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]=1;
a[0]=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(200000);
while(scanf("%lld",&n)==1&&n>0)
{
if(n==1)
{
printf("(3, 5)\n");
continue;
}
j=1;
for(i=6;;i+=6)
{
if(flag[i-1]==0&&flag[i+1]==0)
{
j++;
if(j==n)
{
printf("(%lld, %lld)\n",i-1,i+1);
break;
}
}
}
}
return 0;
}
``````

fahmi
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

### Re: 10394 - Twin Primes

thnx every1.i have got Accepted

meghla
New poster
Posts: 3
Joined: Sat Dec 26, 2009 4:29 pm

### Re:

Yarin wrote:My memory-tight sieve looks like this:
#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd

int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));

I dont know much about bit masking process___ how this process goes on; would you mind to explain how this algorihtm work and also about bit masking.

New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

### Re: 10394 - Twin Primes

Can anyone help me?what can I do to optimise this code??

Code: Select all

``````#include<stdio.h>
bool sieve[20000001];
long int primes[100001];
int main()
{
long int i,j,k,n,c;
sieve[0]=sieve[1]=0;
for(i=2; i<20000001; i++)  sieve[i]=1;
for(i=0; i<4473; i++)
{
if(sieve[i]!=0)
{
for(j=i+1; j<20000001; j++)
{
if(sieve[j]!=0)
{
if((j%i)==0)  sieve[j]=0;
}
}
}
}
j=2;
i=7;
primes[1]=3;
while(i<20000001)
{
if(sieve[i-1]==1 && sieve[i+1]==1)
{
primes[j]=i-1;
j++;
i+=6;
}
else i+=2;
}

while(scanf("%ld",&n)==1)
{

printf("(%ld, %ld)\n",primes[n],primes[n]+2);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10394 - Twin Primes

sadia_atique, you have some large nested loops. Instead of testing every j to see if it's divisible by i, you increment your inner loop by i and then j is the multiples of i, which of course are divisible by i.
Check input and AC output for thousands of problems on uDebug!

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### Re: 10394 - Twin Primes

getting Runtime Error. need help. here is my code
Last edited by ashdboss on Mon Jun 24, 2013 11:19 am, edited 1 time in total.

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 10394 - Twin Primes

your code accessing invalid memory. change the below code portion.

Code: Select all

``````for(j = i+1; (!prime_number[j]);j++) ;
``````
as follows

Code: Select all

``````for(j = i+1; (!prime_number[j]) && j<n;j++) ;
``````
when 'j' is larger than 20000005, then it will definitely lead your code to RE. as per your code the value of 'j' could be larger than 20000005.

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### Re: 10394 - Twin Primes

thanks. it is accepted. it should be less than N.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10394 - Twin Primes

Check input and AC output for over 7,500 problems on uDebug!

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

### Re: 10394 - Twin Primes

Code: Select all

``````import java.util.*;
import java.math.*;
import java.text.*;
import java.lang.*;

class Main
{
public static void main(String abyss[])throws Exception
{
Scanner sc = new Scanner(System.in);

ArrayList<Integer> al = new ArrayList<Integer>();
ArrayList<Integer> prime = new ArrayList<Integer>();
boolean primeCase[] = new boolean[20000001];
Arrays.fill(primeCase, true);
primeCase[0]=primeCase[1]=false;

for(int a=2; a<primeCase.length; a++)
{
if(primeCase[a])
{
for(int b=2; b*a<primeCase.length; b++)
{
primeCase[b*a] = false;
}
}
}
for(int a=3; a<20000001; a++) // checking if prime number and assigning value in arraylist
{
if(primeCase[a]==true)
{
}
}
for(int a=1; a<al.size()-1; a++)
{
if(al.get(a+1)-al.get(a)==2)
{
}
}
while(sc.hasNextLine())
{
String input = sc.nextLine();
if(input.length()==0)
break;

int num = Integer.parseInt(input);
int sum = prime.get(num)+(2);
System.out.println("("+prime.get(num)+", "+sum+")");
}

prime.clear();
al.clear();
}

}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10394 - Twin Primes

That code gets TLE. You could try using BufferedReader and BufferedWriter.
Check input and AC output for thousands of problems on uDebug!

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

### Re: 10394 - Twin Primes

i'm still new to java.. and I don't know how to use Buffered Redear.. hmmm guess i'll be studying it then!! thanks for the advice..