/home/toolbox/public_html/solutions/103/10394/a.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 unsigned 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 int m;
55
56 for (i=0; MAX>i; i++)
57 {
58 /* for */
59 sieve[i] = 0;
60 } /* for */
61
62 /* use odd only,
63 * sieve[0] --> 3 (i*2)+3
64 * sieve[1] --> 5
65 * sieve[2] --> 7
66 * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
67 * 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35
68 */
69 /* do 3 to start things off */
70 /* mark(0, 3); */
71 for (m=3; MAX>m; m=m+3)
72 {
73 /* mark off all multiples */
74 sieve[m] = 1;
75 } /* mark off all multiples */
76 /* now do 5..MAX */
77 for (i=1; (MAX>i)&&(MAX_PAIRS>pCnt); i++)
78 {
79 /* for each possible odd number */
80 if (0 == sieve[i])
81 {
82 /* found a prime */
83 /* mark(i, (i*2)+3); */
84 for (m=(i*3)+3; MAX>m; m=m+(i*2)+3)
85 {
86 /* mark off all multiples */
87 sieve[m] = 1;
88 } /* mark off all multiples */
89 if (0 == sieve[i-1])
90 {
91 /* found a pair */
92 pairs[pCnt] = (i*2)+1;
93 DEBUG printf("Adding: pairs[%d] = %d\n", pCnt, pairs[pCnt]);
94 pCnt++;
95 } /* found a pair */
96 } /* found a prime */
97 } /* for each possible odd number */
98 /* next 3 lines help discover upper limit to reduce runtime */
99 DEBUG printf("pairs[99999] = %d\n", pairs[99998]);
100 DEBUG printf("pairs[100000] = %d\n", pairs[99999]);
101 DEBUG printf("pairs[100001] = %d\n", pairs[100000]);
102 DEBUG printf("pairs found: %d\n", pCnt);
103 } /* FUNCTION init */
104
105 void dump()
106 {
107 /* FUNCTION dump */
108 } /* FUNCTION dump */
109
110 int getInput()
111 {
112 /* FUNCTION getInput */
113 int dataReadFlag;
114
115 dataReadFlag = 1 == scanf(" %d ", &num);
116 return (dataReadFlag);
117 } /* FUNCTION getInput */
118
119 void process()
120 {
121 /* FUNCTION process */
122 printf("(%d, %d)\n", pairs[num], pairs[num]+2);
123 } /* FUNCTION process */
124
125 int main()
126 {
127 /* main */
128 int moreToDo;
129
130 init();
131 moreToDo = getInput();
132 while (moreToDo)
133 {
134 /* while */
135 process();
136 moreToDo = getInput();
137 } /* while */
138
139 return EXIT_SUCCESS;
140 } /* main */
141