Home

c

Prime Time - UVA Online Judge

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1141

 Problem G: Prime Time 

 

The Problem

Euler is a well-known matematician, and, among many other things, he discovered that the formula n^2 + n + 41 produces a prime for 0 <= n < 40. For n = 40, the formula produces 1681, which is 41 * 41. Even though this formula doesn't always produce a prime, it still produces a lot of primes. It's known that for n <= 10000000, there are 47,5% of primes produced by the formula!

So, you'll write a program that will output how many primes does the formula output for a certain interval.

The Input

Each line of input will be given two positive integer a and b such that 0 <= a <= b <= 10000. You must read until the end of the file.

The Output

For each pair a,b read, you must output the percentage of prime numbers produced by the formula in this interval (a <= n <= b) rounded to two decimal digits (with round half up rule).

Sample Input

0 39
0 40
39 40
1423 2222

Sample Output

100.00
97.56
50.00
44.13

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <stdio.h>
#include <math.h>
 
long isprime(long n);
long n2n41(long n);
int primepct[10001];
 
int main(int argc, char **argv)
{
        long a, b, i, ip;
        int notprime, prime;
        for(i = 0; i < 10001; i++)
        {
                        primepct[i] = 0;
        }
        while (scanf("%ld %ld", &a, &b) != EOF)
        {
                for(i = a; i <= b; i++)
                {
                        if(primepct[i-1]==0)
                        {                               
                                if(isprime(n2n41(i))==0)
                                {
                                        prime++;
                                        primepct[i-1] = 1;
                                }
                                else
                                {
                                        notprime++;
                                        primepct[i-1] = -1;
                                }
                        }
                        else
                        {
                                if(primepct[i-1]==1)
                                {
                                        prime++;
                                }
                                else
                                {
                                        notprime++;
                                }
                        }
                }
                printf("%.2f\n", floor(((double)prime/(prime+notprime))*10000+.5)/100);
                notprime = 0;
                prime=0;
        }
        return 0;
}
 
long n2n41(long n)
{
        return n*n+n+41;
}
 
long isprime(long n)
{
        long i = 3;
        long sqn = 0;
        
        while (n%2==0)
        {
                n /= 2;
                return 1;
        }
        sqn = (sqrt(n))+1;
        while (i <= sqn)
        {
                if ((n%i)==0)
                {
                        n /= i;
                        return 1;
                }
                else
                {
                        i += 2;                 
                }
        }
        return 0;
}

Problem 583: UVA Online Judge - Prime Factors

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=524

  Prime Factors 

Webster defines prime as:


prime (prim) n.[ME, fr. MF, fem. of prin first, L primus; akin to L prior] 1 :first in time: original 2 a : having no factor except itself and one (3 is a prime number ) b : having no common factor except one ( 12 and 25 are relatively  ) 3 a : first in rank, authority or significance : principal b : having the highest quality or value (television time) [from Webster's New Collegiate Dictionary]

 


The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e.,

g = f1 x f2 x ... x fn

 

is unique if we assert that fi > 1 for all i and fi <fj for i<j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2p- 1. Euler proved that 231 - 1 is prime in 1772 -- all without the aid of a computer.

 

Input 

The input will consist of a sequence of numbers. Each line of input will contain one number g in the range -231 < g <231, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

 

Output 

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number g > 0, g =  f1 x f2 x ... x fn, where each fi is a prime number greater than unity (with fi <fj for i<j), the format of the output line should be

 

g = f1 x f2 x ... x fn

 

When g < 0, if | g | =  f1 x f2 x ... x fn, the format of the output line should be

g = -1 x f1 x f2 x ... x fn

 

Sample Input 

-190
-191
-192
-193
-194
195
196
197
198
199
200
0

Sample Output 

-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <stdio.h>
#include <math.h>
 
void print_factors(long n);
 
int main(int argc, char **argv)
{
        long n;
        while (1)
        {
                scanf("%ld", &n);
                if (n==0)
                {
                        break;
                }
                printf("%ld = ", n);
                if (n<0)
                {
                        printf("-1 x ");
                        n = -n;
                }
                print_factors(n);
                printf("\n");
        }
        return 0;
}
 
void print_factors(long n)
{
        int first = 1;
        while (n%2==0)
        {
                if (first)
                {
                        printf("2");
                        first = 0;
                }
                else
                {
                        printf(" x 2");
                }
                n /= 2;
        }
        long i = 3;
        long sqn = (sqrt(n))+1;
        while (i <= sqn)
        {
                if ((n%i)==0)
                {
                        if (first)
                        {
                                printf("%ld", i);
                                first = 0;
                        }
                        else
                        {
                                printf(" x %ld", i);
                        }
                        n /= i;
                }
                else
                {
                        i += 2;                 
                }
        }
        if (n>1)
        {
                if(first)
                {
                        printf("%ld", n);
                }
                else
                {
                        printf(" x %ld", n);
                }
        }
}

Problem 713: UVA Online Judge

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=654

Adding Reversed Numbers

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

 
Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

 
ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12) 

Input 

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add. Numbers will be at most 200 characters long. 

Output 

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output. 

Sample Input 

3
24 1
4358 754
305 794 

Sample Output 

34
1998
1

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
void reverse(char str[]);
void add(char num1[], char num2[], char sum[]);
 
int main(int argc, char** argv)
{
        int  n, i;
        char num1[200], num2[200], sum[210];
 
        scanf("%d", &n);
 
        for(i = 0; i < n; i++)
        {
                scanf("%s %s", num1, num2);
                reverse(num1);
                reverse(num2);
                add(num1, num2, sum);
                reverse(sum);
                printf("%s\n", sum);
        }
        return 0;
}
 
void add(char num1[], char num2[], char sum[])
{
        int len1 = strlen(num1);
        int len2 = strlen(num2);
        int len = len1 > len2 ? len1 : len2;
        int i;
        char d1, d2, d3;
        int carry = 0;
        
        reverse(num1);
        reverse(num2);
        
        for(i = 0; i < len; i++)
        {
                if(i < len1)
                {
                        d1 = num1[i] - '0';
                }
                
                if(i < len2)
                {
                        d2 = num2[i] - '0';
                }
                
                d3 = d1 + d2 + carry;
                
                d1 = 0;
                d2 = 0;
                
                if(d3 >=10)
                {
                        carry = 1;
                        sum[i] = (d3 - 10) + '0';
                }               
                else
                {
                        carry = 0;
                        sum[i] = d3 + '0';
                }
        }
        if(carry == 1)
        {
                sum[len] = '1';
                sum[len+1] = '\0';
        }
        else
        {
                sum[len] = '\0';
        }
        
        reverse(sum);
}
 
void reverse(char str[])
{
        int i, length = strlen(str);
        
        for(i = length-1; i >= 0; i--)
        {
                if(str[i] == '0')
                {
                        str[i] = '\0';
                }
                else
                {
                        break;
                }
        }
        
        length = strlen(str);
        int halflength = length / 2;
        for(i = 0; i < halflength; i++)
        {               
                str[i]^=str[length-i-1];
                str[length-i-1]^=str[i];
                str[i]^=str[length-i-1];
        }
}

Problem 100: UVA Online Judge

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

 The 3n + 1 problem 

 

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. 

The Problem

Consider the following algorithm:

 
		1. 		 input n
		2. 		 print n
		3. 		 if n = 1 then STOP
		4. 		 		 if n is odd then  n <-- 3n + 1 
		5. 		 		 else  n <-- n / 2 
		6. 		 GOTO 2
 

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.  

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer. 

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line). 

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

 

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <stdio.h>
 
unsigned long findMaxCycleLength(unsigned long min, unsigned long max);
unsigned long findCycleLength(unsigned long n);
     
int main(int argc, char** argv)
{
        unsigned long min, max, num = 0;
 
        while(scanf("%li %li", &min, &max) != EOF)
        {
                printf("%li %li ", min, max);
                if(min > max)
                {       
                        min^=max;
                        max^=min;
                        min^=max;
                }
                num = findMaxCycleLength(min, max);
                printf("%li\n", num);
        }
}
 
unsigned long findMaxCycleLength(unsigned long min, unsigned long max)
{
        unsigned long temp, i;
        unsigned long n = findCycleLength(max);
 
        for(i = min; i < max; i++)
        {
                temp = findCycleLength(i);
                if(temp > n)
                {       
                        n = temp;
                }
        }
 
        return n;
}
 
unsigned long findCycleLength(unsigned long n)
{
        if(n == 0) return 0;
        unsigned long count = 1;
        while(n != 1)
        {
                if(n%2 == 1)
                {
                        n = 3*n+1;
                }
                else
                {
                        n = n/2;
                }
                count++;
        }
        return count;
}