teratail
回答率
85.47%
質問するログイン新規登録
トップCに関する質問C言語でアトキンの篩を実装したい〈初心者〉

編集履歴

回答編集履歴

1

アトキンの篩のコードに変更

2019/05/22 05:31

投稿

mather
mather

スコア6753

test CHANGED
@@ -1,10 +1,14 @@
1
- 具体的に何が問題か指摘するのが大変なので、まずは関数の定義など基本的な文法から学び直してください。
1
+ まずは関数の定義など基本的な文法から学び直してください。
2
2
 
3
3
  また、定義に立ち返ってアルゴリズムをしっかり確認してみてください。
4
4
 
5
5
 
6
6
 
7
+ 処理が複雑なら分解して関数化する、スコープを小さくして間違いにくくする、というのも手です。
8
+
9
+
10
+
7
- 以下、ちょっと無駄があるサンプルコードです。
11
+ 具体的に何が問題か指摘するのが大変なので、以下にアトキンの篩のコードを書いておきます。
8
12
 
9
13
 
10
14
 
@@ -14,51 +18,201 @@
14
18
 
15
19
 
16
20
 
17
- #define N 1000
21
+ #define N 1000000
22
+
18
-
23
+ #define TRUE 1
24
+
19
-
25
+ #define FALSE 0
20
-
26
+
27
+
28
+
21
- int calc(int i, int j) {
29
+ int is_in(int num, int set[], int length) {
22
-
30
+
23
- return i + j + 2 * i * j;
31
+ for(int i = 0; i < length; i++) {
32
+
24
-
33
+ if(num == set[i]) return TRUE;
34
+
25
- }
35
+ }
36
+
37
+ return FALSE;
38
+
39
+ }
40
+
41
+
42
+
43
+ void toggle(int* target) {
44
+
45
+ if(*target == TRUE) {
46
+
47
+ *target = FALSE;
48
+
49
+ }
50
+
51
+ *target = TRUE;
52
+
53
+ }
54
+
55
+
56
+
57
+ void step1(int is_prime[]) {
58
+
59
+ int n, n60;
60
+
61
+ int s[] = {1,13,17,29,37,41,49,53};
62
+
63
+ int s_len = sizeof(s) / sizeof(s[0]);
64
+
65
+
66
+
67
+ for(int x = 1; 4 * x * x < N; x++) {
68
+
69
+ for(int y = 1; y < N; y = y + 2) {
70
+
71
+ n = 4 * x * x + y * y;
72
+
73
+ if (n > N) break;
74
+
75
+ n60 = n % 60;
76
+
77
+ if(is_in(n60, s, s_len) == TRUE) {
78
+
79
+ toggle(is_prime + n);
80
+
81
+ }
82
+
83
+ }
84
+
85
+ }
86
+
87
+ }
88
+
89
+
90
+
91
+ void step2(int is_prime[]) {
92
+
93
+ int n, n60;
94
+
95
+ int s[] = {7,19,31,43};
96
+
97
+ int s_len = sizeof(s) / sizeof(s[0]);
98
+
99
+
100
+
101
+ for(int x = 1; 3 * x * x < N; x = x + 2) {
102
+
103
+ for(int y = 2; y < N; y = y + 2) {
104
+
105
+ n = 3 * x * x + y * y;
106
+
107
+ if (n > N) break;
108
+
109
+ n60 = n % 60;
110
+
111
+ if(is_in(n60, s, s_len) == TRUE) {
112
+
113
+ toggle(is_prime + n);
114
+
115
+ }
116
+
117
+ }
118
+
119
+ }
120
+
121
+ }
122
+
123
+
124
+
125
+ void step3(int is_prime[]) {
126
+
127
+ int n, n60;
128
+
129
+ int s[] = {11,23,47,59};
130
+
131
+ int s_len = sizeof(s) / sizeof(s[0]);
132
+
133
+
134
+
135
+ for(int x = 2; 3 * x * x < N; x++) {
136
+
137
+ for(int y = x - 1; y > 0; y = y - 2) {
138
+
139
+ n = 3 * x * x - y * y;
140
+
141
+ if (n > N) break;
142
+
143
+ n60 = n % 60;
144
+
145
+ if(is_in(n60, s, s_len) == TRUE) {
146
+
147
+ toggle(is_prime + n);
148
+
149
+ }
150
+
151
+ }
152
+
153
+ }
154
+
155
+ }
156
+
157
+
158
+
159
+ void eliminate_composites(int is_prime[]) {
160
+
161
+ int s[] = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59};
162
+
163
+ int s_len = sizeof(s) / sizeof(s[0]);
164
+
165
+ int n;
166
+
167
+
168
+
169
+ for(n = 7; n*n < N; n++) {
170
+
171
+ if( is_in(n % 60, s, s_len) == TRUE && is_prime[n] == TRUE) {
172
+
173
+ for(int i = 1; i < N/(n*n); i++)
174
+
175
+ is_prime[n*n*i] = FALSE;
176
+
177
+ }
178
+
179
+ }
180
+
181
+ }
182
+
183
+
26
184
 
27
185
 
28
186
 
29
187
  int main(int argc, char* argv[]) {
30
188
 
31
- int list[N+1] = {};
189
+ int is_prime[N+1] = {FALSE};
32
-
190
+
191
+
192
+
33
- int i, j;
193
+ step1(is_prime);
194
+
34
-
195
+ step2(is_prime);
196
+
35
-
197
+ step3(is_prime);
198
+
36
-
199
+ eliminate_composites(is_prime);
200
+
201
+
202
+
203
+ printf("2\n3\n5\n");
204
+
37
- for(i = 1; calc(i, i) <= N; i++) {
205
+ for(int n = 7; n <= N; n++) {
38
-
39
- for(j = i; calc(i, j) <= N; j++) {
206
+
40
-
41
- list[calc(i,j)] = 1;
207
+ if(is_prime[n] == TRUE)
208
+
42
-
209
+ printf("%d\n", n);
210
+
43
- }
211
+ }
44
-
45
- }
212
+
46
-
47
-
48
-
49
- printf("2 ");
213
+
50
-
51
- for(i = 1; i <= N; i++) {
214
+
52
-
53
- if(list[i] == 0) {
215
+ return 0;
54
-
55
- printf("%d ", 2*i + 1);
56
-
57
- }
58
-
59
- }
60
-
61
- printf("\n");
62
216
 
63
217
  }
64
218