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;
}

Intuitive explanation to how dividing by 0 is impossible

We all know a random number times 0 always ends up 0, but the division for 0 is impossible. Computer programs return numerous errors upon stumbling across this matter, math leaners try their best with conditions to avoid dividing by 0. Some guys on YouTube even tried to prove that 1 equals to 0 using this very infamous numerical expression.

But why is that? Let us take a very straightforward and intuitive example to explain why dividing by 0 is a meaningless act.

Say you have a delicious cake. Rashford and Pogba come to your house to eat it with you. In order to make everyone happy, the cake must be divided into 3 equal parts, so each one of you will have a third of that cake. In another scenario, it is the same cake, but you celebrate something alone and want to eat the whole thing. Simple. You divide the cake by 1, so it ends up being itself. Bon appetit!

But what happens when you attempt to divide the cake by 0? The cake just disappears. Just a second ago, a delicious piece of culinary art stays in front of you, but now it is in the void. The act itself gets ridiculous when you think about it. Where is the cake? Ask the divisor.

That is the answer for dividing by 0. You cannot destroy matters, because the act of dividing by 0 “destroys” matters and numbers. For those who studied physics, you must be familiar with the Conservation of mass: “mass can neither be created nor destroyed, although it may be rearranged in space, or the entities associated with it may be changed in form.”

Put plots by Matplotlib to your standard

This post provide the modification for python script for plotting using matplotlib.

plt.rcParams['font.family'] = 'Myriad Pro'
plt.rcParams['font.serif'] = 'Myriad Pro'
plt.rcParams['font.monospace'] = 'PragmataPro Mono Liga'
plt.rcParams['font.size'] = 12
plt.rcParams['axes.labelsize'] = 12
plt.rcParams['axes.labelweight'] = 'bold'
plt.rcParams['axes.titlesize'] = 10
plt.rcParams['xtick.labelsize'] = 10
plt.rcParams['ytick.labelsize'] = 10
plt.rcParams['legend.fontsize'] = 10
plt.rcParams['figure.titlesize'] = 12

Lost Desktop icons after uninstalling Komorebi on Linux Mint

Komorebi is an application that enables animations for desktop wallpapers. When uninstall Komorebi, there is a possibility that desktop will become unresponsive: desklets are still displaying but no icons, right click doesn’t show anything. To fix it, run this code in Terminal:

gsettings set org.nemo.desktop show-desktop-icons true

Thing should be fine after this.

Best way to install Node.js and NPM

I’m writing this post as I need to install node.js and npm to install packages for reveal.js, I’m on Ubuntu 18.04 Bionic.

Normally we can install node.js via terminal by

sudo apt install nodejs

But this is not the best way since the version is outdated and some dependencies won’t meet. The best way to install the latest node.js and npm is via nvm.

curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.8/install.sh | bash

Note that the version number can be checked by going directly to the website and see. The above script will download all the package and put nvm into the Linux alias (so we can use the nvm command globally). After this, log out and log in to activate the alias.

Once you log in, run below script

nvm install node

To update:

nvm install node
nvm alias default nodenvm install node
nvm alias default node

From this answer: https://askubuntu.com/a/1009527

Math Tools

“Mathematicians do not recognize their discipline in such descriptions. We see arithmetic and algebra as tools used in doing mathematics, just as hammers and handsaws are tools used in carpentry. For professionals, mathematics is about curiosity, imagination, and solving problems. There are questions that are instinctive and natural for mathematicians that rarely occur to those looking in from the outside. There is such a thing as a mathematical view of the world. Sadly, it is a view that is too often hidden from those struggling to learn the subject.”
From the book Taking Sudoku seriously

Import mô hình 3D từ Blender vào YADE

Blender là phần mềm thiết kế 3D nguồn mở.

YADE là phần mềm mô hình phần tử rời rạc, cũng nguồn mở.

YADE có thể tạo một khối hình học 3D và hỗ trợ tương đối khiêm tốn: hình hộp, hình cầu, xi-lanh….

Tuy nhiên, những hỗ trợ căn bản của YADE nhiều lúc không phục vụ được nhu cầu thực tế của xây dựng dân dụng. Đặc biệt khi người dùng cần fill particles vào trong một khối có hình dạng ngẫu nhiên. Rất may là YADE có hỗ trợ định dạng GTS và có một công cụ giúp chuyển đổi file từ STL (một dạng file 3D thông dụng từ blender) sang GTS, đó là stl2gts. Câu lệnh để dùng rất đơn giản: ví dụ có một file cube.stl và bạn muốn đổi nó thành cube.gts, cú pháp cần gõ trong terminal như sau:

”’ stl2gts < cube.slt > cube.gts ”’

Thường thì quá trình convert diễn ra khá nhanh. Ngay khi có file gts bạn có thể import vào trong YADE bình thường vì YADE có hỗ trợ python-gts.