แก้ Euler Project 501

มีปัญหา 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)
##

One response to “แก้ Euler Project 501

  1. lp=list(filter(is_prime, range(1, nn//7 +2)))
    a=fd0(lp, lambda x: x**7 <= nn)
    lp=list(filter(is_prime, range(1, nn//8 +2)))
    b=fd0(lp, lambda x, y: x**3 *y <= nn)
    c=fd0(lp, lambda x, y: y**3 *x <= nn)
    lp=list(filter(is_prime, range(1, nn//6 +2)))
    d=fd0(lp, lambda x, y, z: x*y*z <= nn)
    #คอมเมนต์ไว้ก่อน เดี๋ยวมาปรับปรุงครับ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s