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

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

10394

Post by Sajid » Mon Mar 03, 2003 10:10 am

i got this WA. can any1 tell the some critical inputs?
Last edited by Sajid on Sat Oct 25, 2003 6:53 pm, edited 1 time in total.
Sajid Online: www.sajidonline.com

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sun Mar 09, 2003 5:34 pm

there is no critical input for this problem really bcoz u know all possible inputs!! :)

btw try the following input and output:
input:
1
10
100
1000
10000
100000

output:
(3, 5)
(107, 109)
(3821, 3823)
(79559, 79561)
(1260989, 1260991)
(18409199, 18409201)
hope it'll help :)

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid » Sun Mar 23, 2003 10:29 pm

thanx for help

but i m facing problem with the array size, as i m using Turbo C++ 3.0. and so i cant see the value for the all input. then, what can i do now? plz, help...
Sajid Online: www.sajidonline.com

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Mon Mar 24, 2003 2:33 pm

you'd better use VC.
TC wud never support such large array required for this problem. :wink:

thanx
-sohel

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Mar 24, 2003 2:49 pm

but you still can do it in this way:

create algorithm working with array i.e. 1000 elements and before sending solution create bigger array and send such solution. I did problems in this way in BC3.1 long time ago and it's work :) other method is using less memory consuming algorithms ;-))

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Fri Mar 28, 2003 5:43 pm

But it may show output or memory limit exit.
Wt u think about it Michniewski?
i tried with such technic in another prob but didnt worked :roll:

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Mon Apr 07, 2003 1:29 pm

I get TLE. Can anyone help me improve my algorithm?
Last edited by Eric on Wed Apr 09, 2003 12:51 pm, edited 1 time in total.

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Mon Apr 07, 2003 2:50 pm

Change ur algorithm.
Use the algorithm(for twin prime) to reduce unwanted calculation.
WIthout it its not possible to pass TLE
:wink:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Apr 07, 2003 2:57 pm

Jalal, I don't think so ....
If you run program under Windows / DOS you know how much memory you use ... Then If you increase limits, you know memory usage, i.e.

if your table has 1000 elements, and program use 100kB ram, then after change limit to 100000, than your program should use 10MB ram ....

And you know how is maximal limit for your arrays :-)
Other way is counting memory self :)

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Mon Apr 07, 2003 3:04 pm

But how can I improve it?
I need to check all the odd to see if they are prime, shouldn't me?
And the algorithm of checking prime is standard...
Can anyone give me some hints?

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Wed Apr 09, 2003 12:30 am

Thanx Michniewski!
u r right......... :P
eric!
try with the following one :wink:

for(m= 6 ; m < x; m+=6)
if(prime(m-1) && prime(m+1))
printf("%ld %ld\n", m-1, m+1);

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Wed Apr 09, 2003 5:41 am

Thanks. :D
But I only know little about C++ and I can hardly understand your code. :(

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Wed Apr 09, 2003 12:49 pm

Thanks, Jalal.
I change my algorithm and gradually get accepted.
Your post has given me some hint. :D

Max108
New poster
Posts: 5
Joined: Wed Jun 11, 2003 11:24 pm

10394 Bad output or WA? PLZ help!

Post by Max108 » Tue Jun 17, 2003 12:23 am

Hi,

This is my code, it is very simple but it finishes calculationes within the alloted time so thats just fine for me but im getting WA and i dont know why!!!!

[cpp]
#include <fstream.h>
#include <math.h>


/*Returns one if the number is prime, else it returns zero*/
int isPrime(int n)
{
int root = sqrt(n);
for(int i=3; i<root; i+=2)
if(n % i == 0)
return 0;

return 1;
}




void main()
{

long i=0,j;
long calc[100000][2]={3,5};
char *table = new char[18409201];
//ifstream cin;
//cin.open("texto.txt"); //just for testing


/*This is the core of the algorithm*/
for( i=3; i<=4290; i+=2)
if(isPrime(i))
for(j=i+i-1; j<18409201; j+=i)
table[j] = 0;

/*We now store ALL the twin primes*/
for(j=4,i=1; j<=18409201; j+=6)
if(table[j]!=0 && table[j+2]!=0)
{
calc[0]=j+1;
calc[1]=j+3;
i++;
}

/*Get the input and give the output*/
while(cin>>i)
cout<<"("<<calc[i-1][0]<<", "<<calc[i-1][1]<<")"<<endl;


}

[/cpp]


Could some of you guys please help me, I tested it with all the inputs that I culd imagine. is it something about the sapce ASCII32? omg so confused :cry:

Max108
New poster
Posts: 5
Joined: Wed Jun 11, 2003 11:24 pm

confused

Post by Max108 » Tue Jun 17, 2003 12:32 am

can any of you guys tellme whats wrong with my code,
im getting WA

[cpp]

#include <fstream.h>
#include <math.h>


/*Returns one if the number is prime, else it returns zero*/
int isPrime(int n)
{
int root = sqrt(n);
for(int i=3; i<root; i+=2)
if(n % i == 0)
return 0;

return 1;
}


void main()
{

long i=0,j;
long calc[100000][2]={3,5};
char *table = new char[18409201];
//ifstream cin;
//cin.open("texto.txt"); //just for testing


/*This is the core of the algorithm*/
for( i=3; i<=4290; i+=2)
if(isPrime(i))
for(j=i+i-1; j<18409201; j+=i)
table[j] = 0;

/*We now store ALL the twin primes*/
for(j=4,i=1; j<=18409201; j+=6)
if(table[j]!=0 && table[j+2]!=0)
{
calc[0]=j+1;
calc[1]=j+3;
i++;
}

/*Get the input and give the output*/
while(cin>>i)
cout<<"("<<calc[i-1][0]<<", "<<calc[i-1][1]<<")"<<endl;


}
[/cpp]

Post Reply

Return to “Volume 103 (10300-10399)”