UVa : 10650 (Determinate Prime)


// http://uva.onlinejudge.org/external/106/10650.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <bitset>
#include <utility>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1 << 15
using namespace std;

bool mark [N];
vector <int> primeList;

void sieve ()
{
    memset (mark, true, sizeof(mark));

    mark [0] = mark [1] = false;

    for ( int i = 4; i < N; i += 2 )
        mark [i] = false;

    for ( int i = 3; i * i <= N; i += 2 ) {
        if ( mark [i] ) {
            for ( int j = i * i; j < N; j += 2 * i )
                mark [j] = false;
        }
    }

    primeList.clear ();
    primeList.push_back (2);

    for ( int i = 3; i < N; i += 2 ) {
        if ( mark [i] )
            primeList.push_back (i);
    }

    //printf ("%d\n", primeList.size ());
}

void print (int here, int there)
{
    printf ("%d", primeList [here]);

    for ( int i = here + 1; i <= there; i++ )
        printf (" %d", primeList [i]);
    printf ("\n");
}

int main ()
{
    sieve ();

    int x, y;

    while ( scanf ("%d %d", &x, &y) ) {
        if ( x == 0 && y == 0 ) break;

        if ( x > y )
            swap (x, y);

        size_t i = 0;

        while ( primeList [i] < x )
            i++;

        while ( primeList [i + 2] <= y ) {
            if ( primeList [i + 2] - primeList [i + 1] == primeList [i + 1] - primeList [i] ) {
                int startIndex = i;
                int endIndex = i + 2;
                int diff = primeList [i + 1] - primeList [i];
                while ( i + 3 < primeList.size () && primeList [i + 3] - primeList [i + 2] == diff ) {
                    endIndex++;
                    i++;
                }

                if ( primeList [endIndex] <= y ) {
                    if ( startIndex == 0 || primeList [startIndex] - primeList [startIndex - 1] != diff)
                        print (startIndex, endIndex);
                }
                else break;
            }
            i++;
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

One thought on “UVa : 10650 (Determinate Prime)

  1. #include
    #include
    #include
    #include
    using namespace std;

    long long int a[1000000],prime_num[1000000],diff[32001],element[32001];
    long int k=1,i,j;
    void seive()
    {
    long int k=1,i,j;
    memset(a,0,sizeof(a));
    a[0]=0;
    for(i=2;i<1000000;i++)
    {
    if(a[i]==0)
    {
    prime_num[k]=i;
    k++;
    for(j=i;j<1000000;j=j+i)
    {
    a[j]=1;
    }
    }
    }
    }

    void print(int p,int q)
    {
    for(i=p;i<=q;i++)
    printf("%d ",prime_num[i]);
    printf("\n");
    }

    int main()
    {
    seive();
    /*for(i=1;i<20;i++)
    printf("%d %lld\n",i,prime_num[i]);*/
    for(i=0;i<32001;i++)
    {
    diff[i]=prime_num[i]-prime_num[i-1];
    }
    /*for(i=1;i<=60;i++)
    {
    printf("%d %lld\n",i,diff[i]);
    }*/
    for(i=1;i<32001;i++)
    {
    if(diff[i]!=diff[i-1])
    {
    element[i]=2;
    }
    else element[i]=element[i-1]+1;
    }
    /*for(i=1;iy) swap(x,y);
    for(i=0;i<=y;i++)
    {
    if(prime_num[i]==x)
    {
    start_index=i;
    //printf("%d",start_index);
    break;
    }
    }
    int p,q;
    for(i=start_index;prime_num[i]=3 && element[i+1]!=element[i] && prime_num[i-element[i]+1]>=x)
    {
    p=i-element[i]+1;
    q=i;
    }
    }
    print(p,q);
    }
    return 0;
    }

    /*Hi I can not print this one by one can you check plz

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s