Tag Archives: featured

Một bài lập trình hay về số nguyên tố

Số nguyên tố là thứ quá đỗi quen thuộc với những ai học toán, cũng như đối với các lập trình viên. Ai học giải thuật đều đã giải qua những bài về số nguyên tố, với độ khó dàn trải từ đơn giản tới phức tạp, từ vòng lặp thử tính chia hết tới sàng số nguyên tố Eratosthene…

Hôm nay mình rảnh thì có nghĩ ra một bài như thế này, các bạn xem qua nhé!

Đề bài: Cho hai số nguyên dương x và y (các test case đưa vào luôn đảm bảo x > y). Viết chương trình kiểm tra xem x2 – y2 có phải là số nguyên tố hay không.

Thoạt nhìn qua thì bài này khá đơn giản. Tính x2 – y2, rồi kiểm tra. Nhưng khi x và y lớn, ví dụ cỡ 1018 thì cách này sẽ chạy quá thời gian.

Hãy quan sát biểu thức x2 – y2. Nếu bạn đã học 7 hằng đẳng thức đáng nhớ, sẽ dễ thấy rằng x2 – y2 có thể được viết dưới dạng (x-y)(x+y). Vì x và y đều là các số nguyên dương, nên x 1 và y 1. Từ đó suy ra: (x+y) 1.

Xét biểu thức còn lại, x-y. Sẽ xảy ra hai trường hợp là (x-y) 1 và (x-y)=1. Với trường hợp đầu tiên, x2 – y2 sẽ không là số nguyên tố vì vi phạm định nghĩa (chỉ có hai ước là 1 và chính nó). Do đó với (x-y)=1, biểu thức ban đầu sẽ tương đương với chỉ x+y. Ta chỉ cần xét x+y là đủ. Sau đây là code miêu tả bài toán này.

bool primeSquare(long long a, long long b)
{
    if (a-b != 1) return false;
    long long num = a + b;
    if (num % 2 == 0) return false;
    for (long long i = 3; i*i <= num; i += 2)
    {
        if (num % i == 0) return false;
    }
    return true;
}

[Manga Character]: Son Goku – Dragon Ball

(c) image: wakarimasen.fr

My childhood was filled with full of manga and anime series, fairy tales, video games and traditional games with other neighborhood children. The most influencing hobbies motivated me to imagine and draw were manga and anime series that my mom kept searching and buying for me all the time. She’s a wonderful woman.

Although reading quite a lot, Dragon Ball is still one of my 2 favorite manga series along with Doraemon. It even significantly affected to the way I have grown up. Yes, it was just the beginning of my junior high school 21 years ago. There was a long time during my high school years that I wish I were born a boy. However, forget about it. If you are a fan of Dragon Ball, I am sure that you will have specific characters in the series that strongly inspired you. So do I.

I love Son Goku a lot. Continue reading [Manga Character]: Son Goku – Dragon Ball

Preparing a scientific illustration

Making a beaufitul demonstration for your work is very important when you want to bring a clear and interesting message to the readers, especially in academic community.
Thanks to a lot of drawing tools, both open source and commercial, both click-to-draw and code, one can make beautiful and informative piece of artwork that provides better information to enrich the quality of a manuscript. Let us have a look of all available tools out there.

Continue reading Preparing a scientific illustration