ある数より小さい「互いに素」である数の総量を調べたい

Question

ある数より小さい互いに素である数を調べたいです。

例えば 10の場合 [1,3,5,7,9]が互いに素なので、総量は5です。
[2,4,6,8]はお互い2で割り切れてしまうので互いに袖はありません。

途中までのプログラムを↓のように書いています。

def coPrime():
    x=100
    count=0
    primes=[]
    for i in range(1,x):
        if(i==1):
            count+=1
        if(x%i!=0):
            primes.append(i)
            print("i is "+str(i))
            count+=1
    print("count is "+ str(count))

coPrime()

既に出てきた素数をprimesに加えて、iが primesの数で割れれば 互いに素となると思うのですが、ここから進め方がわからず、ご助言いただきたいです。

Comments

[5ugarVVatch1ng]

重箱の隅をつつくことを言いますが
> 例えば 10の場合 [1,3,5,7,9]が互いに素なので
10と5は5で割り切れるので互いに素ではないと思います。

[TakaiY]

「ある数より小さい互いに素である数」とはどのような数ですか？
[1,3,5,7,9]だと、3と9は共通員数3を持つし、ここに[1,3,5,7] としても、[1,5,7,9]としてもよさそうだし、さらにここに 2,4,8の何れかを入れても「1以外に共通員数を持たない数の組」ができるし。

Answer 1

例えば 10の場合 [1,3,5,7,9]が互いに素なので、総量は5です

3 と 9 は互いに素ではないので 10 未満の場合は [1, 2, 3, 5, 7] になるのではないでしょうか(総量は 5 ですが)。

from math import gcd

n = 10
m = range(1, n)
[j for i, j in enumerate(m) if not any(gcd(j,t)!=1 for t in m[:i])]

#
[1, 2, 3, 5, 7]

Comments

[hoshi-takanori]

問題文があいまいではありますが、「互いに素」は 2 つの数の関係なので、ある数 (例えば 10) と互いに素である数の集合と解釈するのが妥当では。「結果集合から任意の 2 数を取り出したときに互いに素である」という条件とは読めないので。また、そう解釈した場合、答えが一意に定まらないような (例えば 3 と 9 が互いに素でないときに 3 を取り除いてもいいわけで。)

Answer 2

iが primesの数で割れれば 互いに素となると思うのですが

ならないと思います。

ある数より小さい互いに素である数を調べたいです。

1. 「互いに素 判定」でググる
2. 1.で判明した判定方法に利用できそうなメソッドがPythonに存在するかググる
3. 1から10まで1.2.を利用してロジックを書く