teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

2

追記

2019/04/28 23:31

投稿

katoy
katoy

スコア22328

answer CHANGED
@@ -4,4 +4,27 @@
4
4
 
5
5
  2 .. n //2 でなく 2, .. n の平方根 までの数で割算を試したほうが計算量が減ります。
6
6
 
7
- さらに言えば、2 以外の偶数での割算は試す必要はありません。
7
+ さらに言えば、2 以外の偶数での割算は試す必要はありません。
8
+
9
+ 追記:
10
+ コード例
11
+ ```python3
12
+ import math
13
+
14
+ def isprimenumber(n):
15
+ if n < 2:
16
+ return false
17
+ if n == 2:
18
+ return True
19
+
20
+ if n % 2 == 0:
21
+ return False
22
+ for i in range(3, int(math.sqrt(n)) + 1, 2):
23
+ if n % i == 0:
24
+ return False
25
+ return True
26
+
27
+ for n in range(2, 100):
28
+ if isprimenumber(n):
29
+ print(n)
30
+ ```

1

追記

2019/04/28 23:30

投稿

katoy
katoy

スコア22328

answer CHANGED
@@ -2,4 +2,6 @@
2
2
  4 は素数ではありません。
3
3
  n = 4 の場合 range(2,n//2) は range(2, 2) となりループが回りません。
4
4
 
5
- 2 .. n //2 でなく 2, .. n の平方根 までの数で割算を試したほうが計算量が減ります。
5
+ 2 .. n //2 でなく 2, .. n の平方根 までの数で割算を試したほうが計算量が減ります。
6
+
7
+ さらに言えば、2 以外の偶数での割算は試す必要はありません。