มีปัญหา Euler Project หมายเลข 501 ให้หาจำนวนตั้งแต่ 1 ถึง 1012 ว่ามีกี่ตัว ที่จำนวนตัวหารซึ่งหารแล้วลงตัวของมันนั้น มีเท่ากับ 8 ตัว
ถ้าใช้วิธีวนลูปตรงๆ คืิอไล่เลข 1 ถึง 1012 ที่ละตัว เอามาหารด้วยเลข 1 จนถึงตัวมันเอง แล้วนับว่ามีหารลงตัวแปดตัวหรือไม่ ช้าแน่ ต้องหาวิธีอื่น โดยใช้หลักคณิตศาตร์มาช่วย คือเมื่อเอาตัวเลขมาแยกตัวประกอบ ให้กลายเป็นผลคูณของจำนวนเฉพาะ ถ้าจำนวนเฉพาะมีซ้ำกันให้เขียนเป็นเลขยกกำลัง จำนวนของตัวหารที่ลงตัว เท่ากับเอาเลขชี้กำลังของแต่ละจำนวนเฉพาะนั้น มาบวกเพิ่มอีกหนึ่งแล้วคูณกัน
เช่น 24 = 2331 เลขชี้กำลังมี 3 และ 1 เอามาบวกเพิ่มอีก 1 จะได้ 4 และ 2 เมื่อคูณกันได้ 8 คือมีจำนวนตัวหารเท่ากับ 8 ตัว (24 นี้มี 1, 2, 3, 4, 6, 8, 12, 24) โดยเลข 8 สามารถได้มาจากการคูณ 8×1, 4×2, 2×4, 2x2x2 ถ้าเราจะไล่หาจำนวนที่มีตัวหารลงตัวแปดตัวโดยทำย้อนไป โดยเอาจำนวนเฉพาะมายกกำลังและคุณกัน โดยเลขชี้กำลังต้องเข้ากับเงื่อนไขที่จะทำให้มีตัวหารลงตัวแปดตัว ก็จะมีได้สี่กรณี
p7
p3q1
p1q3
p1q1r1
โดย 1 < p < q < r และทั้งสามเป็นจำนวนเฉพาะ
ลอง coding คร่าวๆ
##
import itertools
import math
def is_prime(num):
if num < 2:
return False
for x in range(2, int(math.sqrt(num))+1):
if num % x == 0:
return False
else:
return True
def fd0(p, lmbd):
r=0
for x in (itertools.combinations(p, lmbd.__code__.co_argcount)):
if lmbd(*x):
r+=1
return r
nn=100
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t1=a+b+c+d
nn=1000
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t2=a+b+c+d
##
แต่ถ้าทำถึงเลข 1012 ยังช้าอยู่นะครับ ต้องหาทางออกจากวนลูปเอง เมื่อการคูณเกินจำนวนที่กำหนดไว้
##
def is_prime(num):
if num < 2:
return False
x=2
while x*x<=num:
if num % x == 0:
return False
x+=1
return True
nn=10**6
lp=list(filter(is_prime, range(1, nn//6 +2)))
lp.sort()
r=0
for i in range(len(lp)):
if lp[i]**7 > nn:
break
else:
r+=1
for i in range(len(lp)):
for j in range(i+1, len(lp)):
if lp[i]**3 *lp[j] > nn:
break
else:
r+=1
for i in range(len(lp)):
for j in range(i+1, len(lp)):
if lp[j]**3 *lp[i] > nn:
break
else:
r+=1
for i in range(len(lp)):
for j in range(i+1, len(lp)):
if lp[i]*lp[j] > nn:
break
for k in range(j+1, len(lp)):
if lp[i]*lp[j]*lp[k] > nn:
break
else:
r+=1
print(r)
##