USACO: SuperPrime Rib


1. There are only 83 super primes up to 8 digits

2. 1st digit of any super primes must be 2, 3, 5 or 7

3. rest of the digits must be odd numbers 1, 3, 5, 7, 9

4. all 1 digit super primes are: 2, 3, 5, 7
to get all super primes of digits 2, i appended all odd numbers after 1 digit super primes
Here’s the list:
21
23
25
27
29
31
33
35
37
39
51
53
55
57
59
71
73
75
77
79

among these numbers, we will pick only prime numbers
23
29
31
37
53
59
71
73
79

5. to get 3 digits super primes, we append odd numbers after 2 digits super prime
231
233
235
237
239
291
293
295
297
299
311
313
315
317
319
371
373
375
377
379
531
533
535
537
539
591
593
595
597
599
711
713
715
717
719
731
733
735
737
739
791
793
795
797
799
now pick only the prime numbers to get 3 digit super primes

/*
ID: tausiq11
PROG: sprime
LANG: C++
*/

// @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 <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

vector <int> primeRib;
int startIndex;
int endIndex;

bool isPrime (int p)
{
	if ( p % 2 == 0 || p < 1 ) return false;

	int len = sqrt (p * 1.0);

	for ( int i = 3; i <= len; i += 2 ) if ( p % i == 0 ) return false;
	return true;
}

void oneDigit ()
{
	primeRib.push_back (2);
	primeRib.push_back (3);
	primeRib.push_back (5);
	primeRib.push_back (7);

	startIndex = 0;
	endIndex = primeRib.size ();
}

void twoDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();

}

void threeDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void fourDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void fiveDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void sixDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void sevenDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void eightDigit ()
{
	for ( int i = startIndex; i < endIndex; i++ ) {
		for ( int j = 1; j <= 9; j += 2 ) {
			int num = primeRib [i] * 10 + j;
			if ( isPrime (num) ) primeRib.push_back (num);
		}
	}

	startIndex = endIndex;
	endIndex = primeRib.size ();
}

void generatePrimeRib ()
{
	oneDigit ();
	twoDigit ();
	threeDigit ();
	fourDigit ();
	fiveDigit ();
	sixDigit ();
	sevenDigit ();
	eightDigit ();
}

int power (int b, int p)
{
	int ret = 1;

	for ( int i = 1; i <= p; i++ ) 
		ret *= b;

	return ret;
}

int main ()
{
	generatePrimeRib ();

	freopen ("sprime.in", "r", stdin);
	freopen ("sprime.out", "w", stdout);
	//printf ("%d\n", primeRib.size ());

	int digit;
	scanf ("%d", &digit);
	
	for ( size_t i = 0; i < primeRib.size (); i++ ) {
		if ( primeRib [i] >= power (10, digit - 1) && primeRib [i] <= power (10, digit) ) { printf ("%d\n", primeRib [i]); }
	}
	
	return 0;
}

// @END_OF_SOURCE_CODE

2 thoughts on “USACO: SuperPrime Rib

  1. USER: [tausiq11]
    TASK: sprime
    LANG: C++
    
    Compiling...
    Compile: OK
    
    Executing...
       Test 1: TEST OK [0.011 secs, 3024 KB]
       Test 2: TEST OK [0.000 secs, 3024 KB]
       Test 3: TEST OK [0.011 secs, 3024 KB]
       Test 4: TEST OK [0.000 secs, 3024 KB]
       Test 5: TEST OK [0.000 secs, 3024 KB]
    
    All tests OK.
    
    YOUR PROGRAM ('sprime') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations. 
    
  2. what is the problem this code ?plz help me.
    #include
    int s=0,j ;
    int main()
    {
    int a[6],i,flag,n,k;
    scanf(“%d”,&n);
    for(k=1;k<n;k++)
    {s=0;
    for(i=0;i<6;i++)
    scanf("%d",&a[i]);
    for(i=0;i<6;i++)
    {
    flag=1;
    if(a[i]<0)
    {flag=0;
    break;
    }
    }
    for(i=0;i<6;i++)
    {
    if(flag==1)
    { j=a[i];
    if(a[i]!=0)
    j=j+2;
    else

    j=j+1;
    s+=j;
    }
    }
    printf("%d ",s);
    if(s%2==0)
    printf("collection # %d:can be divided",k);
    else
    printf("collection # %d:can't be divided",k);
    }
    return 0;
    }

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