10140 - Prime Distance

[yatsen]

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.

[bolster]

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

[Red Scorpion]

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.

[cytse]

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

[Red Scorpion]

Hi, Cytse

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

Thanks very much.

[cytse]

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

[Red Scorpion]

Thanks, Cytse,

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

Regards,
Red Scorpion.

[horape]

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

How would you do that with 2^32?

Saludos,
HoraPe

[Amir Aavani]

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.

[udvat]

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

[Minilek]

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.

[ibrahim]

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

[clare]

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!

[Martin Macko]

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)

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.

[ebrahim]

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;
}