Euler Project 47 намиране на всички числа, съдържащи 4 фактора - питън, математика, оптимизация

За първи път създавам списък с 10 ^ 6 фалшиви стойности и това, което искам да направя, е да итера True за интервала за всички числа, съдържащи 4 различни основни фактора.

Това означава, че номерът 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:]:

Отговори:

Мисля, че най-лесният начин е да следите какмного първостепенни фактори, които сте намерили за всеки номер. Можете да направите Ситото на Ератостен, но вместо да маркирате кратни на основата като композит, увеличете броя на първите, които ги разделят. Уверете се, че използвате неоптимизирана линия: След като изберете основния p, увеличете броя на primes разделящи p, 2 * p, 3 * p и т.н. вместо да маркирате p ^ 2, p ^ 2 + 2 * p и т.н. композит.

Друга възможност е да запишете най-малкатаосновен фактор за всяко число, докато изпълнявате ситото на Ератостен. Това ви позволява да намерите рекурсивно превъзходната факторизация и можете да проверите кои от тях имат точно 4 основни фактора.

можете ли да го направите обратното: да получите списък на primes до корен (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 и повторете всеки над подходящ номер с още четири вложени втулки! Вероятно все още е по-бързо да го направите по този начин.

PPS след малко мисъл, горният метод щеда бъде значително по-бавен, отколкото просто да използвате модифицираното сито, както се предлага от Дъглас Заре. Докато стигна до 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)

Продължих да правя нещо подобно предиопитвайки сито метод .. И в крайна сметка осъзнавайки, че трябва да използва алгоритъм за търсене, който намира две нечетно число с 4 различни фактори, които се различават по 2 и опитайте числото между тях и числото преди и след. ако това условие е изпълнено, проблемът се решава.

Всъщност тя се връща към същия проблем, както е посочено в публикацията, но чрез някаква магическа теория на числата се свежда до намиране на числа без множество фактори, при които отговарят на условията.

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