[abc 142 D Disjoint Set of Common Divisors] Pythonのロジックエラーについての質問

前提・実現したいこと

Pythonで下記の問題を解いておりましたが、どうしてもある入力に対して間違いを出力します
どこのロジックが間違っているか、ご教示いただけますでしょうか
問題リンク

基本的な考え方は、公約数のうち1と素数の数を数える、という形で考えてます

該当のソースコード

python
1import math
2
3#素数判定
4def trial_division(n):
5    if n == 2:
6        return True
7    if n < 2 or n % 2 == 0:
8        return False
9    for i in range(3, int(math.ceil(math.sqrt(n))) + 1, 2):
10        if n % i == 0:
11            return False
12    return True
13
14#inputをa,bとして受け取り、常にb（2数目）を大きくする処理
15def main():
16    a, b = map(int, input().split())
17    if a > b:
18        dai = a
19        shou = b
20        a = shou
21        b = dai
22        
23
24#iについて1からルートbまでのループを作る。うち、iが１か素数であった場合のみ次の条件へ分岐
25#そのi、もしくはi//bの商のいずれかが、aを割り切った場合（更に商が割り切った場合は、その商が素数だった場合）解答に1追加
26    ans = 0
27    for i in range(int(math.sqrt(b)+1)):
28        if i == 1 or trial_division(i):
29            if b % i == 0:
30                shou = b // i
31
32                if a % i == 0:
33                    ans += 1
34
35                if i != shou and a % shou == 0:
36                    if trial_division(shou):
37                        ans += 1          
38
39    print(ans)
40
41
42
43
44if __name__ == "__main__":
45    main()
46

試したこと

サンプルについて、全出力が正しいことや、境界条件についてみてみる、等はしていますが
間違っている理由を細くできていません
恐れ入りますが、ご指摘いただけますと幸いです

退会済みユーザー

2020/10/15 06:32

たとえば A=10, B=20の場合、期待する答えは[1, 2, 5]の3つになると思います。貼ってもらったコードでは[1, 2]の2つしか検出できないと思うので、まずはそのあたりをチェックしてみては?

sasuke_

2020/10/15 07:19

ありがとうございます！頂いたエラー、iのループの範囲のミスによる影響でした for i in range(math.ceil(math.sqrt(b))+1): というように書き換え、a=10, b=20で回答正しい所、確認しておりますが、まだ間違っている判定が出ます・・・他にも間違っているところあればご指摘いただけますでしょうか

退会済みユーザー

2020/10/15 08:11

A=34, B=68のようなケースを考えてみてください。欲しい回答は[1, 2, 17]の3通りになると思います。現在のように変数の√をとるようなアプローチでは17を取りこぼしてしまいます。

sasuke_

2020/10/16 00:23

ありがとうございました！確かにおっしゃる通りでした。解決できました！

行動規範の内容に同意します

回答1件

自己解決

頂いたご指摘を受け、下記の通り変更しました

python
1
2import math
3
4def trial_division(n):
5    if n == 2:
6        return True
7    if n < 2 or n % 2 == 0:
8        return False
9    for i in range(3, int(math.ceil(math.sqrt(n))) + 1, 2):
10        if n % i == 0:
11            return False
12    return True
13
14def main():
15    a, b = map(int, input().split())
16    if a > b:
17        dai = a
18        shou = b
19        a = shou
20        b = dai
21        
22
23    anslis = []
24    for i in range(1, math.ceil(math.sqrt(b))+2):
25        if b % i == 0:
26            shou = b // i
27
28            if i == 1:
29                anslis.append(i)
30            elif a % i == 0 and trial_division(i):
31                if i not in anslis:
32                    anslis.append(i)
33            if a % shou == 0 and trial_division(shou):
34                if shou not in anslis:
35                    anslis.append(shou)
36    print(len(anslis))
37
38
39if __name__ == "__main__":
40    main()
41
42