ข้อนี้จะมีจำนวนตั้งแต่ A ถึง B

โดยจะมีเลขจำนวนเฉพาะอย่างน้อย P

ถ้าเลขระหว่าง A ถึง B ตัวไหนหารด้วยจำนวนเฉพาะลงตัว จะถือว่าเลขเหล่านั้นอยู่กลุ่มเดียวกัน

และถ้ามีตัวเลขไหนสามารถหารด้วยจำนวนเฉพาะ 2 ตัวลงตัว


กลุ่มของจำนวนเฉพาะ 2 ตัวนั้นจะรวมกันเป็นกลุ่มเดียวกัน

อ่านต่อ ที่นี่



ข้อนี้เขียนเป็น functional ค่อนข้างลำบาก

เช่น จำนวนเฉพาะอาจจะต้องใช้ Sieve

การจัดกลุ่มต้องใช้ Disjoint Set

ซึ่ง data structure ดังกล่าวเป็นแบบ mutable



ข้อดีของ f# อีกอย่างคือ ไม่ใช่ pure functional

หากจำเป็นต้องใช้ mutable data structure ก็ไม่มีปัญหา



เริ่มจาก Prime

let prime = Prime()

อันนี้ผมใช้ prime ที่เขียนเอง อ่านเพิ่มได้ ที่นี่



เริ่มเลย

let solve A B P =
    let mutable size = int (B - A + 1L)
    let primes = prime.FromRange(P, B-A)
    let set = DisjointSet()

size เป็น การประกาศแบบ mutable ซึ่งจะแก้ค่าได้ภายหลัง

primes คือ จำนวนเฉพาะระหว่าง P ถึง B-A

set ก็คือ disjoint set เขียนเองก็ได้ครับ logic ตาม wiki

for p in primes do
    let start = ((A - 1L)/p + 1L)*p
    for n in {start+p..p..B} do
        if set.Union(start, n) then
            size <- size - 1
 
size |> string

ทีนี้ก็ loop ตาม prime แต่ละตัว

ไล่หาตัวที่หารด้วย prime ลงตัว จาก A ถึง B

แล้วเอาค่าที่ได้ union เข้า disjoint set

ถ้า union สำเร็จก็หัก size ไป 1



ทำจนจบก็ได้คำตอบครับ