嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

Problem 47 Distinct primes factors 2016-11-10 12:32:00

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7

15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

这题走了不少弯路,首先是一个很大弯路的解法:

import math

CHECK = 4
last = 0
c = 0

PRIME_LIST = []


def product(list):
    p = 1
    for i in list:
        p *= i
    return p


def is_Prime(number):
    if number < 2:
        return False
    for x in range(2, int(math.sqrt(number)) + 1):
        if number % x == 0:
            return False
    return True

for i in range(2, 1000):
    if is_Prime(i):
        PRIME_LIST.append(i)


def check_Prime(number, p_list, start):
    global last
    global c
    if start < number and is_Prime(number):
        if p_list:
            final = list(set(p_list + [number]))
            # final = p_list + [number]
            if len(final) == CHECK:
                result = product(p_list + [number])
                print result, '=',
                for j in p_list:
                    print "%s x" % j,
                print number
                if (last + 1 == result) or last == 0:
                    last = result
                    c += 1
                else:
                    last = result
                    c = 1
                if c == CHECK:
                    for i in reversed(range(0, CHECK)):
                        print result - i,
                    exit(0)
            return
        else:
            return
    for i in PRIME_LIST:
        if i < start:
            continue
        if i > number / 2:
            break
        if not is_Prime(i):
            continue
        if number % i == 0:
            check_Prime(number / i, p_list + [i], i)


i = 1
while True:
    i += 1
    check_Prime(i, [], 2)

其实思路也什么大问题,不就是分解质因数嘛,[Finished in 230.6s]

然后是一个知道答案之后的改进解法:

import math

CHECK = 4
last = 0
c = 0

PRIME_LIST = []
PRIME_RANGE = 400000


def is_Prime(number):
    if number < 2:
        return False
    for x in range(2, int(math.sqrt(number)) + 1):
        if number % x == 0:
            return False
    return True

for i in range(2, PRIME_RANGE):
    if is_Prime(i):
        PRIME_LIST.append(i)


def process(number):
    temp = number
    result = 0
    for prime in PRIME_LIST:
        if prime > temp:
            break
        if temp % prime == 0:
            result += 1
            while temp % prime == 0:
                temp /= prime
    return result

i = 2 * 3 * 5 * 7
while True:
    count = process(i)
    if count == CHECK:
        if last + 1 == i:
            c += 1
        else:
            c = 1
        last = i
        if c == CHECK:
            print i - 3, i - 2, i - 1, i
            break
    i += 1

不要问我上面的40W是怎么来的数字,就是一个magic number。结果是[Finished in 19.5s],主要是把素数先算了一个列表出来,分解质因数也不记录分解成什么了。

评论共