UVa : 516 (Prime Land)


Critical Cases

/* Critical input *******************
18 1 17 1 15 1
17 1 11 1
11 1 29 1 9 1
2 1 4 1 5 1 7 1 11 1
18 1 23 1 29 1
31 1 29 1
2 3 11 2 25 1
41 2
51 1 5 1
17 1 19 1 23 1
0
*/

/* Critical output *******************
353 1 13 1
31 1 3 1 2 1
41 1 7 1 5 1 2 1
3079 1
7 4 5 1
449 1 2 1
3457 1 7 1
7 1 5 1 3 1 2 4
127 1 2 1
619 1 3 1 2 2
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int prime_frq [2] [3600];

int produce_number (char a [])
{
	int length = strlen (a);
	int i = 0;
	int j = 0;
	int k = 0;
	char ch [10];
	int number [1000];

	while ( i < length ) {
		if ( a [i] == ' ' ) {
			ch [j] = '';
			number [k++] = atoi (ch);
			j = 0;
		}

		else
			ch [j++] = a [i];
		i++;
	}

	ch [j] = '';
	number [k++] = atoi (ch);

	i = 0;
	int sum = 1;
	while ( i < k ) {
		sum *= pow (number [i], number [i+1]);
		i += 2;
	}

	return sum;
}


int is_prime (int x)
{
	int length = (int) sqrt (x);

	for ( int i = 2; i <= length; i++ ) {
		if ( x % i == 0 )
		return 0;
	}
	return 1;
}


void produce_prime ()
{
	int i;

	prime_frq [0] [0] = 2;
	int k = 1;

	for ( i = 3; i < 32768; i += 2 ) {
		if ( is_prime (i) )
		prime_frq [0] [k++] = i;
	}
}


void frequency (int x)
{
	for ( int i = 0; i < 3512; i++ )  {
		if ( prime_frq [0] [i] == x ) {
			prime_frq [1] [i] ++;
			return;
		}
	}
}


int main(int argc, char **argv)
{
	char a [10000];
	int i;

	produce_prime ();

	while ( gets (a) ) {

		for ( i = 0; i < 3600; i++ )
			prime_frq [1] [i] = 0;

		if ( ! atoi (a) )
		return 0;

		int x = produce_number (a);
		x--;

		if ( is_prime (x) )
		printf("%d %d", x, 1);

		else {
			int divisor = 1;
			while ( x > 1 ) {
				divisor++;
				while ( x % divisor == 0 ) {
					frequency (divisor);
					x /= divisor;
				}
			}
		}

		int flag = 0;
		for ( i = 3511; i >= 0; i-- ) {
			if ( prime_frq [1] [i] != 0 ) {
				if ( flag )
					printf(" %d %d", prime_frq [0] [i], prime_frq [1] [i]);
				else
				printf ("%d %d", prime_frq [0] [i], prime_frq [1] [i]);
				flag = 1;
			}
		}
		printf("\n");

	}
	return 0;
}

Advertisements

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