Kiểm tra 1 số có phải là số nguyên tố không bằng 3 cách trong Elixir
TIL
589
elixir
32
White

Vũ viết ngày 04/02/2018

Kiểm tra 1 số có phải là số nguyên tố không bằng 3 cách trong Elixir

Giả sử ta có sẵn 1 hàm span(from, to) giúp trả về 1 list các số nguyên từ from đến to

Cách 1: Dùng build in function

    defmodule MyInteger do
      def prime?(2), do: true
      def prime?(n) do
        Enum.all?(span(2, :math.sqrt(n)), &(rem(n, &1) != 0))
      end
    end

Cách 2: Dùng list comprehensions

    defmodule MyInteger do 
      def prime?(2), do: true
      def prime?(n) do
        list = for i <- span(2, :math.sqrt(n)), rem(n, i) == 0, do: false
        case list do 
          [] -> true
          [_] -> false
        end
      end
    end

Cách 3: Dùng đệ quy

    defmodule MyInteger do 
      def prime?(2), do: true
      def prime?(n), do: prime?(n, 2)
      defp prime?(n, i) when rem(n, i) == 0, do: false
      defp prime?(n, i) when i * i > n, do: true
      defp prime?(n, i), do: prime?(n, i + 1)
    end

Phân tích từng cách làm

Với cách 1 dùng build in function của Elixir thì không có gì đáng nói. Vì mục đích học tập nên mình thử tự implement, từ đó có cách 2 và 3.

Với cách 2, ban đầu mình định làm là cho lặp qua mảng từ 2 đến căn bậc 2 của n, nếu n chia hết cho bất kì phần tử nào trong mảng thì sẽ trả về false ngay lập tức, như cách nhiều ngôn ngữ khác có từ khóa để break out khỏi hàm ngay. Nhưng đến khi làm đc nửa đường rồi mới phát hiện ra trong Elixir lại không có hỗ trợ việc đó (hoặc có lẽ mình google không ra :trollface:) nên phải đổi hướng.

Với mỗi lần lặp, filter xem n có chia hết cho i không, nếu có trả về false, không thì chuyển qua vòng lặp tiếp theo. Kết quả của vòng lặp này sẽ đc chia làm 2 trường hợp: 1 là list gồm toàn false, 2 là list rỗng. Nếu list rỗng thì số n là số nguyên tố, và ngược lại.

Nhược điểm của cách này là ta sẽ phải xử lí cho đến phần tử cuối cùng trong list mới có thể biết được kết quả của hàm.

Cách 3, mình vận dụng pattern-matching function và đệ quy để làm. Nếu n chia hết cho i thì ta có thể trả về false ngay lập tức, còn không thì tiếp tục gọi đệ quy với i + 1, cho đến khi i * i > n thì trả về true.

Vu 05-02-2018

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

1 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Bài viết liên quan
White
0 2
fCC: Technical Documentation Page note So I have finished the HTML part of this exercise and I want to come here to lament about the lengthy HTML ...
HungHayHo viết 27 ngày trước
0 2
White
19 1
Toán tử XOR có tính chất: + A XOR A = 0 + 0 XOR A = A Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về runtime, và với O(1)...
kiennt viết gần 2 năm trước
19 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
1 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!