10394 - Twin Primes
Moderator: Board moderators
The problem is that the contents of your array table is undefined. You could initialize it with either:
[c]memset(table, 1, 18409201);[/c]
or by just looping over all elements and setting them to some nonzero value. Otherwise it seems to work fine. I notice that you call the isPrime in the sieve loop, why not look it up in table instead? It would save you some time when running the program.
Best regards
[c]memset(table, 1, 18409201);[/c]
or by just looping over all elements and setting them to some nonzero value. Otherwise it seems to work fine. I notice that you call the isPrime in the sieve loop, why not look it up in table instead? It would save you some time when running the program.
Best regards
-
- New poster
- Posts: 2
- Joined: Tue Jul 15, 2003 2:49 pm
10394
I think my source makes output in time, but I got TLE. ㅜ_ㅜ
plz check this.
[cpp]#include <iostream>
#include <cmath>
using namespace std;
int prime1[10000];
bool prime2[20000000];
void main(void)
{
int c1, c2;
int input=0;
bool p;
for(c1=2; c1<=4473; c1++)
{
p=true;
for(c2=2; c2<sqrt(c1); c2++)
{
if(c1%c2==0)
{
p=false;
break;
}
}
if(p)
{
prime1[input++]=c1;
}
}
for(c1=0; c1<20000000; c1++)
{
prime2[c1]=true;
}
for(c1=0; c1<input; c1++)
{
for(c2=2; c2<=10000000; c2++)
{
if(c2*prime1[c1]>=20000000) break;
prime2[c2*prime1[c1]]=false;
}
}
int t1=0;
while(1)
{
cin >> input;
t1++;
if(cin.eof()) break;
if(input<0) break;
c2=0;
for(c1=2; c1<20000000; c1++)
{
if(prime2[c1+2] && prime2[c1])
{
c2++;
}
if(c2==input)
{
cout << "(" << c1 << ", " << c1+2 << ")" << endl;
break;
}
}
if(t1==10000) break;
}
}[/cpp]
plz check this.
[cpp]#include <iostream>
#include <cmath>
using namespace std;
int prime1[10000];
bool prime2[20000000];
void main(void)
{
int c1, c2;
int input=0;
bool p;
for(c1=2; c1<=4473; c1++)
{
p=true;
for(c2=2; c2<sqrt(c1); c2++)
{
if(c1%c2==0)
{
p=false;
break;
}
}
if(p)
{
prime1[input++]=c1;
}
}
for(c1=0; c1<20000000; c1++)
{
prime2[c1]=true;
}
for(c1=0; c1<input; c1++)
{
for(c2=2; c2<=10000000; c2++)
{
if(c2*prime1[c1]>=20000000) break;
prime2[c2*prime1[c1]]=false;
}
}
int t1=0;
while(1)
{
cin >> input;
t1++;
if(cin.eof()) break;
if(input<0) break;
c2=0;
for(c1=2; c1<20000000; c1++)
{
if(prime2[c1+2] && prime2[c1])
{
c2++;
}
if(c2==input)
{
cout << "(" << c1 << ", " << c1+2 << ")" << endl;
break;
}
}
if(t1==10000) break;
}
}[/cpp]
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am
the algorithm is great.Jalal wrote:Thanx Michniewski!
u r right.........
eric!
try with the following one![]()
for(m= 6 ; m < x; m+=6)
if(prime(m-1) && prime(m+1))
printf("%ld %ld\n", m-1, m+1);
but..how do u guys discover that all twins prime are subset of (6*k-1,6*k+1), for k is integers?
however, i am still TLE using this algorithm, why?
[cpp]
#include <iostream>
using namespace std;
int i,j,k,n;
int prime[100005];
int counter;
int isprime(int);
void main(void)
{
prime[1]=3;
prime[2]=5;
counter=3;
for (i=12;counter<=100002;i+=6)
{
if (isprime(i-1) && isprime(i+1))
{
prime[counter++]=i-1;
}
}
while (1)
{
cin>>n;
if (cin.eof())
break;
cout<<"("<<prime[n]<<", "<<prime[n]+2<<")"<<endl;
}
}
int isprime(int get)
{
int k;
for (k=3;k*k<=get;k+=2)
{
if (get % k ==0)
return 0;
}
return 1;
}
[/cpp]
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am
-
- Learning poster
- Posts: 57
- Joined: Wed Dec 10, 2003 7:32 pm
- Location: Russia, Saint-Petersburg
HOW DO IT FASTER?
I read all posts about this problem but can`t uderstand how I can optimize my program. It`s work very slow...
[pascal]
program acm10394; {Twince Prime Numbers}
{type integer = longint;}
const maxn = 4500;
koltw = 100000;
var ck : array[1 .. maxn] of boolean;
list : array[1 .. 700] of integer;
tw : array[1 .. koltw] of integer;
n, l : integer;
procedure get_primes; {Eratosphen}
var i, j: integer;
begin
fillchar(ck, sizeof(ck), true);
for i := 3 to 67 do
if ck then begin
j := i * i;
while j <= maxn do begin
ck[j] := false;
j := j + i;
end;
end;
list[1]:=2; l:=1;
i:=1;
while i<=maxn do begin
inc(i, 2);
if ck then begin
inc(l);
list[l] := i;
end;
end; {number of prime numbers - l}
end;
function be_prime( x : integer) : boolean; {prime or not}
var i,j : integer;
begin
j := trunc(sqrt(x));
be_prime := false;
i:=2;
while list <= j do begin
if x mod list = 0 then exit;
inc(i);
end;
be_prime := true;
end;
procedure twins;
var i, k: integer;
begin
tw[1]:=3; i:=1; k:=0;
while i<koltw do begin
inc(k, 6);
if be_prime(k-1) then
if be_prime(k+1) then begin
inc(i);
tw:=k-1;
end;
end;
end;
begin
{ assign(input, 'input.txt');
reset(input);}
get_primes;
twins;
while not eof do begin
readln(n);
writeln('(', tw[n], ', ', tw[n]+2, ')');
end;
end.
[/pascal][/pascal]
[pascal]
program acm10394; {Twince Prime Numbers}
{type integer = longint;}
const maxn = 4500;
koltw = 100000;
var ck : array[1 .. maxn] of boolean;
list : array[1 .. 700] of integer;
tw : array[1 .. koltw] of integer;
n, l : integer;
procedure get_primes; {Eratosphen}
var i, j: integer;
begin
fillchar(ck, sizeof(ck), true);
for i := 3 to 67 do
if ck then begin
j := i * i;
while j <= maxn do begin
ck[j] := false;
j := j + i;
end;
end;
list[1]:=2; l:=1;
i:=1;
while i<=maxn do begin
inc(i, 2);
if ck then begin
inc(l);
list[l] := i;
end;
end; {number of prime numbers - l}
end;
function be_prime( x : integer) : boolean; {prime or not}
var i,j : integer;
begin
j := trunc(sqrt(x));
be_prime := false;
i:=2;
while list <= j do begin
if x mod list = 0 then exit;
inc(i);
end;
be_prime := true;
end;
procedure twins;
var i, k: integer;
begin
tw[1]:=3; i:=1; k:=0;
while i<koltw do begin
inc(k, 6);
if be_prime(k-1) then
if be_prime(k+1) then begin
inc(i);
tw:=k-1;
end;
end;
end;
begin
{ assign(input, 'input.txt');
reset(input);}
get_primes;
twins;
while not eof do begin
readln(n);
writeln('(', tw[n], ', ', tw[n]+2, ')');
end;
end.
[/pascal][/pascal]
SilVer DirectXer:
Aside from 2, every prime number is odd. So q and q + 2 must both be odd, as both are prime. Hence, q + 1 is even. i.e. q + 1 is divisible by 2.
For any three consecutive integers, exactly one of them is divisible by 3. So either q = 3 and q + 2 = 5 [as 3 | q, q prime => q = 3] or q + 1 is divisible by 3. [And 3 | q + 2 is extraneous since, as before, it would require q + 2 = 3 => q = 1, which isn't prime].
Hence, the twin primes are (3, 5) or (q, q + 2) where q + 1 is divisible by 2 * 3 = 6. The result now follows.
As for the sieve method for generating primes, see an article about Eratosthenes' Sieve, e.g. http://mathworld.wolfram.com/EratosthenesSieve.html
pavelph:
I'm sorry, but I don't know Pascal very well. But, I think that calling be_prime() in twins() is the cause of the slowness since you'll end up calling it so many times.
Let q and q + 2 be twin primes. The number between them is (clearly) q + 1.but..how do u guys discover that all twins prime are subset of (6*k-1,6*k+1), for k is integers?
Aside from 2, every prime number is odd. So q and q + 2 must both be odd, as both are prime. Hence, q + 1 is even. i.e. q + 1 is divisible by 2.
For any three consecutive integers, exactly one of them is divisible by 3. So either q = 3 and q + 2 = 5 [as 3 | q, q prime => q = 3] or q + 1 is divisible by 3. [And 3 | q + 2 is extraneous since, as before, it would require q + 2 = 3 => q = 1, which isn't prime].
Hence, the twin primes are (3, 5) or (q, q + 2) where q + 1 is divisible by 2 * 3 = 6. The result now follows.
As for the sieve method for generating primes, see an article about Eratosthenes' Sieve, e.g. http://mathworld.wolfram.com/EratosthenesSieve.html
pavelph:
I'm sorry, but I don't know Pascal very well. But, I think that calling be_prime() in twins() is the cause of the slowness since you'll end up calling it so many times.
I am getting RTE in my program. Please help me to find my bug. Here is my code:
[c]#include <stdio.h>
#include <math.h>
const int max = 20000000;
char p[2500100];
#define isprime(n) (p[n/8] & (1<<(7-n % 8 )))
void seive()
{
int i,j;
for(i=3; i<=max; i+=2)
p[i/8] = p[i/8]|(1<<7-i % 8 );
int lim = sqrt(max);
for(i=3; i<=lim; i+=2)
if((p[i/8] & (1<<(7-i % 8 ))))
for(j=i; i*j<=max; j+=2)
p[i*j/8] = p[i*j/8] & ~(1<<7-(i*j) % 8 );
}
void main()
{
seive();
long s[100100];
long i, j;
for(i=3, j=1; j<100010; i+=2)
if(isprime(i) && isprime(i+2))
s[j++] = i;
while(1==scanf("%ld", &i))
printf("(%ld, %ld)\n", s, s+2);
}
[/c]
[c]#include <stdio.h>
#include <math.h>
const int max = 20000000;
char p[2500100];
#define isprime(n) (p[n/8] & (1<<(7-n % 8 )))
void seive()
{
int i,j;
for(i=3; i<=max; i+=2)
p[i/8] = p[i/8]|(1<<7-i % 8 );
int lim = sqrt(max);
for(i=3; i<=lim; i+=2)
if((p[i/8] & (1<<(7-i % 8 ))))
for(j=i; i*j<=max; j+=2)
p[i*j/8] = p[i*j/8] & ~(1<<7-(i*j) % 8 );
}
void main()
{
seive();
long s[100100];
long i, j;
for(i=3, j=1; j<100010; i+=2)
if(isprime(i) && isprime(i+2))
s[j++] = i;
while(1==scanf("%ld", &i))
printf("(%ld, %ld)\n", s, s+2);
}
[/c]
10394
This problem seemed to me easy. But very often a simple looking problem makes us crazy by fooling. I have received Run Time Error but don't know why. Please help me.
Here's my code:
..........deleted later
Here's my code:
..........deleted later
Last edited by Ferdous on Sun Mar 07, 2004 12:11 pm, edited 1 time in total.
I am destined to live on this cruel world........
right
Hi Ferdous,
Try to make the twin and prime array global.
that is;
[c]
char prime[MAX+1];
long twin[100005];
int main()
{
}
[/c]
Declaring huge arrays in the main function is the cause of RTE.
Hope it helps.
![:wink:](./images/smilies/icon_wink.gif)
Try to make the twin and prime array global.
that is;
[c]
char prime[MAX+1];
long twin[100005];
int main()
{
}
[/c]
Declaring huge arrays in the main function is the cause of RTE.
Hope it helps.
![:wink:](./images/smilies/icon_wink.gif)
As far I know, the main function is a procedure which has a limited amount of data area.
So if you declare a large array inside main, it tries to use the limited data area of main, which of course is smaller than the array size, hence the program crashes.
But if you declare it global, it is located in a seperate memory area, which can handle such big array.
So if you declare a large array inside main, it tries to use the limited data area of main, which of course is smaller than the array size, hence the program crashes.
But if you declare it global, it is located in a seperate memory area, which can handle such big array.