欧拉计划47找到包含4个因子的所有数字 [英] Euler Project 47 finding all numbers contaning 4 factors

问题描述

我首先创建一个包含10 ^ 6个假值的列表，我要做的是在包含4个不同素数的所有数字的区间上迭代True.

I first create a list of 10^6 false values and what I want to do is to iterate True over the interval for all numbers containing 4 distinct prime factors.

这意味着数字2 * 2 * 3 * 5 * 7是包含4个不同质数的数字.

What that means is that the number 2 * 2 * 3 * 5 * 7 is a number containing 4 distinct prime numbers.

我真的不知道如何创建数字，我什至不知道如何去思考.我想有4种不同的数字，但数量可能不同.到目前为止的代码:

I really have no clue how to create the numbers, I don't even know how to think of the it. I want to have 4 different kinds of numbers but in all possible different amounts. Code as far:

""" 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:]:

推荐答案

我认为最简单的方法是跟踪找到的每个数字有多少个素因.您可以执行Eratosthenes筛分法，但不要将素数的倍数标记为复合数，而应增加素数除以它们的数量.确保使用未优化的循环:一旦选择了质数p，请增加除以p，2 * p，3 * p等的质数计数，而不是标记p ^ 2，p ^ 2 + 2 * p等.合成的.

I think the easiest way is to keep track of how many prime factors you have found for each number. You can perform the Sieve of Eratosthenes, but instead of marking multiples of a prime as composite, increment the count of primes dividing them. Make sure that you use an unoptimized loop: Once you choose the prime p, increment the count of primes dividing p, 2*p, 3*p etc. instead of marking p^2, p^2+2*p, etc. composite.

另一种可能性是在执行Eratosthenes筛时记录每个数字的最小素因数.这使您可以递归地找到素因数分解，并且可以检查其中哪些正好有4个素因数.

Another possibility is to record the smallest prime factor of each number as you perform the Sieve of Eratosthenes. This lets you find the prime factorization recursively, and you can check which of these have exactly 4 prime factors.

这篇关于欧拉计划47找到包含4个因子的所有数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！