teratail
回答率
85.47%
質問するログイン新規登録
トップJavaに関する質問ＰＥ１２　三角数の約数の数を求める処理が遅い

編集履歴

回答編集履歴

2

バグ修正とコメント添削

2018/08/15 15:26

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -12,17 +12,47 @@
12
12
 
13
13
  ```java
14
14
 
15
- static void func2(int num) {
15
+ public static void main(String[] args) {
16
+
17
+ long start = System.currentTimeMillis();
16
18
 
17
19
 
18
20
 
19
- int n = 0; //n //n個目（の三角数）
21
+ func(500);
20
22
 
21
- int n1 = 0; //n+1 //n+1
22
23
 
23
- int t = 0; //triangle //三角数
24
24
 
25
+ long end = System.currentTimeMillis();
26
+
27
+ System.out.println((end - start) + "ms");
28
+
29
+ }
30
+
31
+
32
+
33
+ static void func(int num) {
34
+
35
+
36
+
37
+ int n = 0; //自然数n
38
+
39
+ int t = 0; //n番目の三角数（総和）
40
+
41
+
42
+
43
+ //約数の個数の性質「互いに素なaとbについて、
44
+
45
+ //a*bの約数の個数は、aの約数の個数×bの約数の個数に等しい」
46
+
47
+ //nとn+1は互いに素なのでnかn+1のどちらかが偶数になる
48
+
49
+
50
+
51
+ int x = 0; //(偶数奇数で分けて偶数の方を2で割る)
52
+
53
+ int y = 0; //(偶数奇数で分けて偶数の方を2で割る)
54
+
25
- int d = 0; //divisors //三角数の約数の個数
55
+ int d = 0; //分けて計算した約数の個数を掛けた総数
26
56
 
27
57
 
28
58
 
@@ -30,85 +60,113 @@
30
60
 
31
61
 
32
62
 
63
+ //自然数n
64
+
33
65
  n++;
34
66
 
35
67
 
36
68
 
37
- n1 = n + 1;
69
+ //三角数の公式
70
+
71
+ //n(n+1)/2
38
72
 
39
73
 
40
74
 
41
- t = n * n1 / 2; //三角数の公式　n(n+1)/2
75
+ //n 1 2 3 4 5 6 7 8 9 10
76
+
77
+ //三角数 1 3 6 10 15 21 28 36 45 55
78
+
79
+ //約数　 1 2 4 4 4 4 6 9 6 4
42
80
 
43
81
 
44
82
 
45
- //「nとn+1のうち、偶数を2で割ったもの」
46
-
47
- // 奇数偶数で分けて計算して掛ける
83
+ //偶数奇数判定
48
84
 
49
85
  if (n % 2 == 0) {
50
86
 
51
- d = getDivisors(n / 2) * getDivisors(n1);
87
+ x = n / 2;
88
+
89
+ y = n + 1;
52
90
 
53
91
  } else {
54
92
 
93
+ x = n;
94
+
95
+ y = (n + 1) / 2;
96
+
97
+ }
98
+
99
+
100
+
101
+ //個別に約数の個数を求め掛け合わせて総数を求める
102
+
55
- d = getDivisors(n) * getDivisors(n1 / 2);
103
+ d = getD(x) * getD(y);
104
+
105
+ }
106
+
107
+
108
+
109
+ //ログ出力用
110
+
111
+ t = n * (n + 1) / 2;
112
+
113
+
114
+
115
+ System.out.print("last n:" + (n));
116
+
117
+ System.out.print(" t:" + t);
118
+
119
+ System.out.print(" d:" + d);
120
+
121
+ System.out.println();
122
+
123
+ System.out.println("Ans:" + t);
124
+
125
+ }
126
+
127
+
128
+
129
+ //約数の個数を求める
130
+
131
+ static int getD(final int t) {
132
+
133
+
134
+
135
+ int d = 0;
136
+
137
+
138
+
139
+ final int rootT = (int) Math.sqrt(t);
140
+
141
+
142
+
143
+ for (int i = 1; i <= rootT; i++) {
144
+
145
+ if (t % i == 0) {
146
+
147
+ d++;
56
148
 
57
149
  }
58
150
 
59
151
  }
60
152
 
61
- System.out.println("n:" + n + " t:" + t + " d:" + d);
62
153
 
154
+
63
- System.out.println("Answer:" + t);
155
+ d *= 2;
64
156
 
65
157
 
66
158
 
159
+ if (t == rootT * rootT) {
160
+
161
+ d--;
162
+
67
- }
163
+ }
68
164
 
69
165
 
70
166
 
71
- //三角数の約数の個数を求める
72
-
73
- //範囲は三角数の平方根まで
74
-
75
- //三角数が平方数の場合は+1する
76
-
77
- static int getDivisors(int triangle) {
78
-
79
-
80
-
81
- int divisors = 0;
82
-
83
- int rootT = (int) Math.sqrt(triangle);
84
-
85
-
86
-
87
- for (int i = 1; i <= rootT; i++) {
88
-
89
- if (triangle % i == 0) {
90
-
91
- divisors++;
92
-
93
- }
94
-
95
- }
96
-
97
- divisors = divisors * 2;
98
-
99
-
100
-
101
- if (triangle == rootT * rootT) {
102
-
103
- divisors++;
104
-
105
- }
106
-
107
- return divisors;
167
+ return d;
108
168
 
109
169
  }
110
-
111
-
112
170
 
113
171
  ```
114
172
 
@@ -116,12 +174,8 @@
116
174
 
117
175
  ---
118
176
 
119
- n:12375 t:76576500 d:576
177
+ last n:12375 t:76576500 d:576
120
178
 
121
- Answer:76576500
179
+ Ans:76576500
122
180
 
123
- 7ms
181
+ 0ms
124
-
125
-
126
-
127
- （307ms※平方根までの処理を実装前の結果）

1

未実装の修正を追加

2018/08/15 15:25

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -1,6 +1,8 @@
1
1
  頂いたアドバイスで作り直したところ、かなり改善できました。
2
2
 
3
3
  ありがとうございました。
4
+
5
+ ※追加で平方根の処理を実装したところ更に改善できました。
4
6
 
5
7
 
6
8
 
@@ -12,19 +14,19 @@
12
14
 
13
15
  static void func2(int num) {
14
16
 
15
-
17
+
16
18
 
17
19
  int n = 0; //n //n個目（の三角数）
18
20
 
19
- int n1= 0; //n+1
21
+ int n1 = 0; //n+1 //n+1
20
22
 
21
23
  int t = 0; //triangle //三角数
22
24
 
23
- int d = 0; //divisors //三角数の約数の個数
25
+ int d = 0; //divisors //三角数の約数の個数
24
26
 
25
-
26
27
 
28
+
27
- while(d < num) {
29
+ while (d < num) {
28
30
 
29
31
 
30
32
 
@@ -32,45 +34,57 @@
32
34
 
33
35
 
34
36
 
35
- n1 = n+1;
37
+ n1 = n + 1;
36
38
 
37
-
38
39
 
39
- t = n*n1/2; //三角数の公式　n(n+1)/2
40
40
 
41
-
41
+ t = n * n1 / 2; //三角数の公式　n(n+1)/2
42
+
43
+
42
44
 
43
45
  //「nとn+1のうち、偶数を2で割ったもの」
44
46
 
45
47
  // 奇数偶数で分けて計算して掛ける
46
48
 
47
- if(n % 2 == 0) {
49
+ if (n % 2 == 0) {
48
50
 
49
- d = getDivisors(n/2) * getDivisors(n1) ;
51
+ d = getDivisors(n / 2) * getDivisors(n1);
50
52
 
51
53
  } else {
52
54
 
53
- d = getDivisors(n) * getDivisors(n1/2) ;
55
+ d = getDivisors(n) * getDivisors(n1 / 2);
54
56
 
55
57
  }
56
58
 
57
59
  }
58
60
 
59
- System.out.println("n:"+n+" t:"+t+" d:"+d );
61
+ System.out.println("n:" + n + " t:" + t + " d:" + d);
62
+
63
+ System.out.println("Answer:" + t);
64
+
65
+
60
66
 
61
67
  }
62
68
 
63
-
64
69
 
70
+
65
- //約数の個数を求める
71
+ //三角数の約数の個数を求める
72
+
73
+ //範囲は三角数の平方根まで
74
+
75
+ //三角数が平方数の場合は+1する
66
76
 
67
77
  static int getDivisors(int triangle) {
68
78
 
69
-
79
+
70
80
 
71
81
  int divisors = 0;
72
82
 
83
+ int rootT = (int) Math.sqrt(triangle);
84
+
85
+
86
+
73
- for (int i = 1; i <= triangle; i++) {
87
+ for (int i = 1; i <= rootT; i++) {
74
88
 
75
89
  if (triangle % i == 0) {
76
90
 
@@ -80,9 +94,21 @@
80
94
 
81
95
  }
82
96
 
97
+ divisors = divisors * 2;
98
+
99
+
100
+
101
+ if (triangle == rootT * rootT) {
102
+
103
+ divisors++;
104
+
105
+ }
106
+
83
107
  return divisors;
84
108
 
85
109
  }
110
+
111
+
86
112
 
87
113
  ```
88
114
 
@@ -94,4 +120,8 @@
94
120
 
95
121
  Answer:76576500
96
122
 
97
- 307ms
123
+ 7ms
124
+
125
+
126
+
127
+ （307ms※平方根までの処理を実装前の結果）