10394 - Twin Primes

[fahmi]

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]

thnx every1.i have got Accepted

[meghla]

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.

[sadia_atique]

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]

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.

[ashdboss]

getting Runtime Error. need help. here is my code

[t.tahasin]

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.
Hope this will help you.

[ashdboss]

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

[uDebug]

Replying to follow the thread.

[AbyssalGreed]

I don't know why this is RE, can someone please help me??
thanks in advance..

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;
				}
			}
		}
		al.add(0,2);
		for(int a=3; a<20000001; a++) // checking if prime number and assigning value in arraylist
		{
			if(primeCase[a]==true)
			{
				al.add(al.size(),a);
			}
		}
		prime.add(0,2);
		for(int a=1; a<al.size()-1; a++)
		{
			if(al.get(a+1)-al.get(a)==2)
			{
				prime.add(prime.size(), al.get(a));
			}
		}
		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]

That code gets TLE. You could try using BufferedReader and BufferedWriter.

[AbyssalGreed]

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..