最初に10 ^ 6個の偽の値のリストを作成し、私がやりたいことは4つの異なる素因数を含むすべての数について区間にわたってTrueを繰り返すことです。
つまり、2 * 2 * 3 * 5 * 7という数は、4つの異なる素数を含む数です。
数字の作り方については全くわかりませんが、考え方さえ分からないのですが、4種類の数字を持つことができますが、可能な限り金額を変えたいのです。
""" Pre do prime list """
sieve = [True] * 1000
sieve[0] = sieve[1] = False
def primes(sieve, x):
for i in range(x+x, len(sieve), x):
sieve[i] = False
for x in range(2, int(len(sieve) ** 0.5) + 1):
primes(sieve, x)
PRIMES = list((x for x in range(2, len(sieve)) if sieve[x]))
""" Main """
Numbers = [False] * 10 ** 6
Factors = PRIMES[0] * PRIMES[1] * PRIMES[2] * PRIMES[3]
Numbers[Factors] = True
for prime in PRIMES:
for prime in PRIMES[1:]:
for prime in PRIMES[2:]:
for prime in PRIMES[3:]:
回答：
回答№1は1私は最も簡単な方法は方法を追跡することであると思いますあなたがそれぞれの数について見つけた多くの主な要因。 Sieve of Eratosthenesを実行することはできますが、素数の倍数を合成としてマークする代わりに、素数をそれらの値で割った数を増やします。最適化されていないループを使用していることを確認してください。素数pを選択したら、p ^ 2、p ^ 2 + 2 * pなどをマークする代わりに、素数をp、2 * p、3 * pなどで割ってカウントを増やします。複合。
他の可能性は最も小さいを記録することですSieve of Eratosthenesを実行するときの各数字の素因数。これにより、素因数分解を再帰的に見つけることができ、どれが厳密に4つの素因数を持つかを確認できます。
回答№2の場合は0
あなたはそれを逆にすることができますか：ルート（N）まで素数のリストを取得し、N未満である製品を生成します。
res = {}
for i in range(n):
for j in range(i,n):
for k in range(j,n):
for m in range(k,n):
prod = p[i] * p[j] * p[k] * p[m]
if prod < N:
res[prod] = [p[i], p[j], p[k], p[m]]
編気付いた distinct それで、あなたはそれぞれのp [] ** uを置き、別の4つの入れ子になったループで適切な数にわたってそれぞれを反復しなければならないでしょう！この方法でラウンドを実行するほうがまだ速いでしょう。
少し考えた後のPPS、上記の方法はDouglas Zareによって提案されているように、修正されたふるいを使用するよりも著しく遅くなります。私が10 ** 6になるまでに私の最初の提案は数分かかりますが、変更されたふるいは10秒以下です
class Numb(object):
def __init__(self):
self.is_prime = True
self.pf = []
def tick(self, factor):
self.is_prime = False
self.pf.append(factor)
N = 1000000
sieve = [Numb() for i in range(N)]
sieve[0].is_prime = sieve[1].is_prime = False
def primes(sieve, x):
for i in range(x + x, len(sieve), x):
sieve[i].tick(x)
for x in range(2, int(len(sieve) ** 0.5) + 1):
if sieve[x].is_prime:
primes(sieve, x)
回答№3の場合は0
私は前に、このようなことを続けましたふるい法を試してみてください。そして最後に、私は2つの異なる4つの異なる因子を持つ2つの奇数を見つけ、その間の数と前後の数を試す探索アルゴリズムを使うべきだと気づいた。この条件が満たされれば問題は解決します。
それは実際にはpostで述べたのと同じ問題に頼っていますが、いくつかの数論を通して、魔法は質問条件が満たされるところの倍数の因数のない数を見つけることに帰着します。
Factors = list([0, 0, 1, 1, 2, 1, 2, 1, 3, 2]) + [0] * 5 * 10 ** 5
for prime in PRIMES:
Factors[prime] = 1
for number in range(10, 5 * 10 ** 5):
if Factors[number] == 1:
continue
for prime in PRIMES:
if number % prime == 0:
Factors[number] = Factors[prime] + Factors[number // prime]
break