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
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
Post
by fahmi » Sat Jan 10, 2009 9:13 pm
thnx every1.i have got Accepted
meghla
New poster
Posts: 3 Joined: Sat Dec 26, 2009 4:29 pm
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
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
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
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
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
Post
by ashdboss » Mon Jun 24, 2013 11:20 am
thanks.
it is accepted. it should be less than N.
uDebug
A great helper
Posts: 475 Joined: Tue Jul 24, 2012 4:23 pm
Post
by uDebug » Mon Apr 21, 2014 12:05 pm
Replying to follow the thread.
AbyssalGreed
New poster
Posts: 9 Joined: Mon Aug 25, 2014 5:25 am
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
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
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..