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

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

Re: 10394 - Twin Primes

Post by fahmi » Sat Jan 10, 2009 6:29 pm

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

Post by fahmi » Sat Jan 10, 2009 9:13 pm

thnx every1.i have got Accepted :lol:

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

Re:

Post by meghla » Fri Mar 05, 2010 9:23 pm

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.

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

Re: 10394 - Twin Primes

Post by sadia_atique » Fri Dec 23, 2011 4:06 pm

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

Post by brianfry713 » Thu Jan 19, 2012 2:45 am

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

Post by ashdboss » Mon Jun 24, 2013 9:10 am

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

Post by t.tahasin » Mon Jun 24, 2013 11:11 am

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
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

Re: 10394 - Twin Primes

Post by ashdboss » Mon Jun 24, 2013 11:20 am

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

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

Re: 10394 - Twin Primes

Post by uDebug » Mon Apr 21, 2014 12:05 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

Re: 10394 - Twin Primes

Post by AbyssalGreed » Wed Sep 03, 2014 9:22 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10394 - Twin Primes

Post by brianfry713 » Wed Sep 03, 2014 8:04 pm

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

Post by AbyssalGreed » Thu Sep 04, 2014 1:49 am

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

Post Reply

Return to “Volume 103 (10300-10399)”