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^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]，主要是把素数先算了一个列表出来，分解质因数也不记录分解成什么了。