Số nguyên tố – Prime Integer

Số nguyên tố thì ai cũng biết rồi, rất đơn giản. Tuy nhiên trong lý thuyết cũng như ứng dụng của ngành mật mã, số nguyên tố có vai trò rất quan trọng. Sau đây, là một số bài toán/problems đơn giản trong toán học cũng như trong lập trình, có liên quan đến số nguyên tố.

Một số link tham khảo :

Xác định một số nguyên là số nguyên tố

Số nguyên tố là số chia hết cho chính nó và 1. Vậy muốn biết một nguyên n là số nguyên tố hay không bằng lập trình, cách đơn giản nhất là kiểm tra nó có chia hết cho số nào từ 2 cho số đến n-1, nếu không nó là số nguyên tố.

#Check whether a integer is prime or not
def isPrimeInteger(n):
    for i in range(2, n - 1):
        if (n % i == 0):
            return False

    return True


print(isPrimeInteger(13))

Tìm các số nguyên tố nhỏ hơn số nguyên n cho trước

# Find prime numbers less than n
def getPrimeIntegersLessThan(n):
    primeIntegers = []
    for i in range(2,n):
        if(isPrimeInteger(i)):
            primeIntegers.append(i);
    return primeIntegers;

print(getPrimeIntegersLessThan(100));

Tìm ước lớn nhất của số nguyên n cho trước

Thuật toán :

  • Lược qua các số nguyên tố nhỏ a hơn n bắt đầu từ 2. Kiểm tra n có chia hết cho a, nếu có thì ước lớn nhất của nó hoặc là a hoặc n/a là ước chung lớn nhất của a.
def theGreatestCanBeDividedNumberBy(n):
    for i in range(2,n):
        if(isPrimeInteger(i) and n%i == 0):
            return max(n/i,i);


print(theGreatestCanBeDividedNumberBy(30));

Phân tích thành thừa số nguyên tố của một số nguyên n cho trước

def primeFactorizationOf (n, primeFactorization):
    for i in range(2,n+1):
        if(isPrimeInteger(i) and n%i == 0):
            primeFactorization.append(i);
            primeFactorizationOf(int(n/i), primeFactorization);
            break;

    return primeFactorization;

Tìm GCD của 2 số nguyên cho trước a và b

GCD là là ước chung lớn nhất của 2 số nguyên tố a và b. Viết tắt của chữ Greatest Common Divisor.

Thuật toán : Phân tích a,b ra các thừa số nguyên tố. Tìm các thừa số nguyên tố chung của a và b, rồi nhân lại. Kết quả là ước chung lớn nhất của a và b.

def gcd (a,b):
    primeFactorizationOfa = [];
    primeFactorizationOf(a,primeFactorizationOfa)
    primeFactorizationOfb = [];
    primeFactorizationOf(b,primeFactorizationOfb);
    samevalues = [];
    for i in primeFactorizationOfa:
        if(i in primeFactorizationOfb):
            primeFactorizationOfb.remove((i));
            samevalues.append(i);
    gcdValue = 1;
    for samevalue in samevalues:
        gcdValue *= samevalue;
    return gcdValue;

Một số từ vựng Tiếng Anh liên quan:

Số nguyên tố : Prime Integer
Số bị chia : Dividen
Số chia : Divisor
Thương số : quotient
Số dư : Remainder
Ước chung lớn nhất: Greatest Common Divisor

Leave a Reply

Your email address will not be published. Required fields are marked *