/home/toolbox/public_html/solutions/103/10394/j.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date:
18 * Purpose: fun
19 * Problem:
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 /*
27 #define MAX 10000002
28 #define MAX_PAIRS 100010
29 */
30 #define MAX 9204601
31 #define MAX_PAIRS 100002
32
33 int num;
34 char sieve[MAX];
35 int pairs[MAX_PAIRS];
36 int pCnt = 1;
37
38 void mark(int strt, int increment)
39 {
40 /* FUNCTION mark */
41 int i;
42
43 for (i=strt+increment; MAX>i; i=i+increment)
44 {
45 /* mark off all multiples */
46 sieve[i] = 1;
47 } /* mark off all multiples */
48 } /* FUNCTION mark */
49
50 void init()
51 {
52 /* FUNCTION init */
53 int i;
54
55 for (i=1; MAX>i; i++)
56 {
57 /* for */
58 sieve[i] = 0;
59 } /* for */
60
61 /* use odd only,
62 * sieve[0] --> 3 (i*2)+3
63 * sieve[1] --> 5
64 * sieve[2] --> 7
65 * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
66 * 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35
67 */
68 /* do 3 to start things off */
69 mark(0, 3);
70 /* now do 5..MAX */
71 for (i=1; (MAX>i)&&(MAX_PAIRS>pCnt); i++)
72 {
73 /* for each possible odd number */
74 if (0 == sieve[i])
75 {
76 /* found a prime */
77 mark(i, (i*2)+3);
78 if (0 == sieve[i-1])
79 {
80 /* found a pair */
81 pairs[pCnt] = (i*2)+1;
82 DEBUG printf("Adding: pairs[%d] = %d\n", pCnt, pairs[pCnt]);
83 pCnt++;
84 } /* found a pair */
85 } /* found a prime */
86 } /* for each possible odd number */
87 /* next 3 lines help discover upper limit to reduce runtime */
88 DEBUG printf("pairs[99999] = %d\n", pairs[99998]);
89 DEBUG printf("pairs[100000] = %d\n", pairs[99999]);
90 DEBUG printf("pairs[100001] = %d\n", pairs[100000]);
91 DEBUG printf("pairs found: %d\n", pCnt);
92 } /* FUNCTION init */
93
94 void dump()
95 {
96 /* FUNCTION dump */
97 } /* FUNCTION dump */
98
99 int getInput()
100 {
101 /* FUNCTION getInput */
102 int dataReadFlag;
103
104 dataReadFlag = 1 == scanf(" %d ", &num);
105 return (dataReadFlag);
106 } /* FUNCTION getInput */
107
108 void process()
109 {
110 /* FUNCTION process */
111 printf("(%d, %d)\n", pairs[num], pairs[num]+2);
112 } /* FUNCTION process */
113
114 int main()
115 {
116 /* main */
117 int moreToDo;
118
119 init();
120 moreToDo = getInput();
121 while (moreToDo)
122 {
123 /* while */
124 process();
125 moreToDo = getInput();
126 } /* while */
127
128 return EXIT_SUCCESS;
129 } /* main */
130