OJ Board

Posted: **Fri Nov 23, 2001 12:12 pm**

I got Time Limit Exceeded.
I can realize because the distance between L and U is so large.
Could anyone give me some hint to solve this problem? Thanx.

Posted: **Sun Nov 25, 2001 12:04 am**

Generate the first 70,000 or so primes, and use those, combined with a sieve.

Posted: **Fri Feb 07, 2003 12:34 pm**

Can Someone give me the clue to solve P 10140 ?

I know that the number is very large. (<=2,147,483,647),
How can I know that the number between L and U, whose is prime
or not ? (I use iteration from L and U, and this is very consuming
time) >>> (At first I generates 70.000 th primes, and store it).

If someone has time, please help me.

Regards,
Red Scorpion.

Posted: **Sat Feb 08, 2003 8:56 am**

You may try using the Sieve of Eratosthenes to find prime numbers.

Posted: **Sat Feb 08, 2003 9:18 am**

Hi, Cytse

I never heard what is "The Sieve of Eratosthenes",
can you explain what algo it is ?

Thanks very much.

Posted: **Mon Feb 10, 2003 6:01 am**

You may search for it with google. There are hundreds of websites talking about it.

Posted: **Mon Feb 10, 2003 9:58 am**

Thanks, Cytse,

Now I know what is "The Sieve of Eratosthenes".

Regards,
Red Scorpion.

Posted: **Fri Dec 05, 2003 11:19 pm**

cytse wrote:You may try using the Sieve of Eratosthenes to find prime numbers.

How would you do that with 2^32?

Saludos,
HoraPe

Posted: **Tue May 18, 2004 1:50 pm**

hi

if you read the problem more carefully, you can see that the problem says , |L- U|< 1000000.
i means that you must do Sieve of Eratosthenes on an array with maximum length of 1000000.

Posted: **Fri Aug 06, 2004 11:28 am**

I solved the problem and getting WA.but failed to find my bug.
wud anyone plz give me some sample input/output?help in advance

Posted: **Sat Aug 07, 2004 2:56 am**

Good luck.

Input:

Code: Select all

2147483647 2147483647
2146483647 2147483647
1 2
1 10
2 3
2 10
1 1000001
550 9214
500000 1500000
4 5
4 7
5 7
5 5
5 6
1500000 1500001
1500000 1500000
1500006 1500019
1500006 1500018
1500007 1500018
1500007 1500019
1500008 1500019
1500008 1500018

Output:

Code: Select all

There are no adjacent primes.
2146483811,2146483813 are closest, 2146841093,2146841273 are most distant.
There are no adjacent primes.
2,3 are closest, 3,5 are most distant.
2,3 are closest, 2,3 are most distant.
2,3 are closest, 3,5 are most distant.
2,3 are closest, 492113,492227 are most distant.
569,571 are closest, 1327,1361 are most distant.
500111,500113 are closest, 1357201,1357333 are most distant.
There are no adjacent primes.
5,7 are closest, 5,7 are most distant.
5,7 are closest, 5,7 are most distant.
There are no adjacent primes.
There are no adjacent primes.
There are no adjacent primes.
There are no adjacent primes.
1500007,1500019 are closest, 1500007,1500019 are most distant.
There are no adjacent primes.
There are no adjacent primes.
1500007,1500019 are closest, 1500007,1500019 are most distant.
There are no adjacent primes.
There are no adjacent primes.

Posted: **Thu Jun 16, 2005 3:28 pm**

More hints please. Sir, i can't think any process.

Posted: **Sun Aug 27, 2006 4:28 pm**

Hello!
I am getting TLE on this problem, although I found the list of prime numbers using sieve algorithm.

Could someone plz take a look at my code and give me a hint to get AC

Here it is:

#include<iostream>
#include<stdio.h>

using namespace std;

int main()
{
int L, U;
while(cin>>L>>U)
{
int j;
int d = U-L+1;
bool *flag = new bool[d];
for(int t=0; t<d; t++)
flag[t]=true;
for(int j=(L%2!=0); j<d; j+=2)
flag[j]=false;
for(int i=3; i*i<=U; i+=2)
{
if(i>L and flag[i-L]==false)
continue;
j=L/i*i;
if(j<L)
j+=i;
if(j==i)
j+=i;
j-=L;
for(;j<d; j+=i)
flag[j]=false;
}
if(L<=1)
flag[1-L]=false;
if(L<=2)
flag[2-L]=true;

int primes[100000];
int pr = 0;
for(int f=0; f<d; f++)
{
if(flag[f])
{
primes[pr]=L+f;
pr++;
}
}
int min = 1000000;
int max = 0;
int c1 =-1, c2=-1, d1=-1, d2=-1;
for(int y = 1; y<pr; y++)
{
int test = primes[y]-primes[y-1];
if(test>max)
{
d1 = primes[y-1];
d2 = primes[y];
max = test;
}
if(test<min)
{
c1 = primes[y-1];
c2 = primes[y];
min = test;
}

}
if(c1!=-1 and c2!=-1)
printf("%d,%d are closest, %d,%d are most distant.\n",c1,c2,d1,d2);
else
printf("There are no adjacent primes.\n");

}
}

Thanx!

Posted: **Sun Aug 27, 2006 9:10 pm**

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=2278)

forum 'Volume CI' description wrote:All about problems in Volume CI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Posted: **Wed Jan 10, 2007 1:31 am**

I tested my code with all I/O found in the forum and it works, but it gets W.A on the online judge.
Please take a look at my code or provide some I/O.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

//#define DEBUG 1

#if DEBUG
#define dump(fmt, x) fprintf(stderr, #x " = " fmt "\n", x)
#else
#define dump(fmt, x)
#endif

#define MAXINT ((1<<31) - 1)
#define MAXP (1<<16)

int primes[MAXP];
int nprimes = 0;

int main()
{
        bool comp[MAXP] = {0};
        for (int i = 2; i < MAXP; ++i)
                if (!comp[MAXP])
                {
                        primes[nprimes++] = i;
                        for (int j = i; j < MAXP; j += i)
                                comp[j] = true;
                }

        int m, n;
        while (scanf("%d %d", &m, &n) == 2)
        {
                if (m > n)
                        n ^= m ^= n ^= m;
                m >?= 2;
                dump("%d", m);
                dump("%d", n);
                int len = n - m;
                bool isprime[len+1];
                memset(isprime, 1, sizeof(isprime));
                for (int i = 0; i < nprimes; ++i)
                {
                        int pr = primes[i];
                        for (int j = (pr - m % pr) % pr; j <= len; j += pr)
                                if (pr < m + j)
                                        isprime[j] = false;
                }

                int min = MAXINT;
                int mina, minb;
                int max = 0;
                int maxa, maxb;
                int last = 0;
                if (m == 2 && n > 2)
                {
                        last = 1;
                        min = 1;
                        mina = 0;
                        minb = 1;
                        max = 1;
                        maxa = 0;
                        maxb = 1;
                }
                else
                        for (int k = 0; k <= len; ++k)
                                if (isprime[k])
                                {
                                        last = k;
                                        break;
                                }
                dump("%d", last);
                for (int k = last + 2; k <= len; k += 2)
                        if (isprime[k])
                        {
                                int d = k - last;
                                if (d < min)
                                {
                                        min = d;
                                        mina = last;
                                        minb = k;
                                }
                                if (d > max)
                                {
                                        max = d;
                                        maxa = last;
                                        maxb = k;
                                }
                                last = k;
                        }
                if (max == 0)
                        puts("There are no adjacent primes.");
                else
                        printf("%d,%d are closest, %d,%d are most distant.\n", mina + m, minb + m, maxa + m, maxb + m);
        }
        return 0;
}

OJ Board

10140 - Prime Distance

10140 - Prime Distance

10140

10140-prime distance

10140 TLE

Re: 10140 TLE

10140-Prime Distance WA