Lập trình Java

Các thuật toán về số nguyên tố trong Java

Posted on by Đỗ Thành
10
Th5
View: 27

Java cung cấp một số thuật toán để kiểm tra số nguyên tố. Dưới đây là một số thuật toán phổ biến trong Java:

Kiểm tra số nguyên tố bằng cách kiểm tra từng số chia hết cho số đó

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Kiểm tra số nguyên tố bằng cách sàng Eratosthenes

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    boolean[] primes = new boolean[num + 1];
    Arrays.fill(primes, true);
    primes[0] = false;
    primes[1] = false;
    for (int i = 2; i * i <= num; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= num; j += i) {
                primes[j] = false;
            }
        }
    }
    return primes[num];
}

Kiểm tra số nguyên tố bằng cách sàng Sundaram

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    int limit = (num - 2) / 2;
    boolean[] sieve = new boolean[limit + 1];
    Arrays.fill(sieve, true);
    for (int i = 1; i <= limit; i++) {
        for (int j = i; i + j + 2 * i * j <= limit; j++) {
            sieve[i + j + 2 * i * j] = false;
        }
    }
    return sieve[(num - 2) / 2];
}

Kiểm tra số nguyên tố bằng cách sàng Atkin

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    boolean[] sieve = new boolean[num + 1];
    Arrays.fill(sieve, false);
    int sqrt = (int) Math.sqrt(num);
    for (int x = 1; x <= sqrt; x++) {
        for (int y = 1; y <= sqrt; y++) {
            int n = 4 * x * x + y * y;
            if (n <= num && (n % 12 == 1 || n % 12 == 5)) {
                sieve[n] ^= true;
            }
            n = 3 * x * x + y * y;
            if (n <= num && n % 12 == 7) {
                sieve[n] ^= true;
            }
            n = 3 * x * x - y * y;
            if (x > y && n <= num && n % 12 == 11) {
                sieve[n] ^= true;
            }
        }
    }
    for (int i = 5; i <= sqrt; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= num; j += i * i) {
                sieve[j] = false;
            }
        }
    }
    return sieve[num

Kiểm tra số nguyên tố bằng cách sàng của Euler

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
    for (int prime : primes) {
        if (num == prime) {
            return true;
        }
        if (num % prime == 0) {
            return false;
        }
    }
    int d = num - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    for (int prime : primes) {
        int a = Math.min(num - 2, prime);
        int m = modularExponentiation(a, d, num);
        if (m == 1 || m == num - 1) {
            continue;
        }
        boolean composite = true;
        for (int i = 0; i < s - 1; i++) {
            m = modularExponentiation(m, 2, num);
            if (m == num - 1) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Chú ý rằng sử dụng các thuật toán kiểm tra số nguyên tố là một phần quan trọng trong lĩnh vực mã hóa và bảo mật, và việc chọn thuật toán phù hợp phụ thuộc vào mục đích sử dụng cũng như kích thước của số cần kiểm tra.

Kiểm tra số nguyên tố bằng cách sử dụng Miller-Rabin

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int d = num - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    int[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    for (int base : bases) {
        if (base >= num) {
            break;
        }
        int x = modularExponentiation(base, d, num);
        if (x == 1 || x == num - 1) {
            continue;
        }
        boolean composite = true;
        for (int i = 0; i < s - 1; i++) {
            x = modularExponentiation(x, 2, num);
            if (x == num - 1) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Trong đó, thuật toán Miller-Rabin là một trong những thuật toán kiểm tra số nguyên tố nhanh nhất hiện có và được sử dụng rộng rãi trong thực tế.

Kiểm tra số nguyên tố bằng cách sử dụng AKS

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3 || num == 5) {
        return true;
    }
    if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
        return false;
    }
    int r = 1;
    while (r * r <= num) {
        r++;
    }
    int[] a = new int[r + 1];
    Arrays.fill(a, 1);
    for (int i = 2; i <= r; i++) {
        if (a[i] == 1) {
            for (int j = i * i; j <= r; j += i) {
                a[j] = 0;
            }
            int k = 1;
            while (Math.pow(i, k) <= r) {
                int p = (int) Math.pow(i, k);
                int m = num % p;
                int q = num / p;
                if (q < p) {
                    for (int n = 1; n <= q; n++) {
                        int x = m - n * p;
                        if (x >= 0 && a[n] == 1 && a[x] == 1) {
                            return false;
                        }
                    }
                    break;
                }
                if (a[m] == 0) {
                    return false;
                }
                k++;
            }
        }
    }
    return true;
}

Thuật toán AKS được coi là một trong những thuật toán kiểm tra số nguyên tố nhanh nhất hiện có. Tuy nhiên, nó không phù hợp cho các số lớn và tốn nhiều bộ nhớ.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Miller

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int d = num - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    int[] bases = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
    for (int base : bases) {
        if (base >= num) {
            break;
        }
        int x = modularExponentiation(base, d, num);
        if (x == 1 || x == num - 1) {
            continue;
        }
        boolean composite = true;
        for (int i = 0; i < s - 1; i++) {
            x = modularExponentiation(x, 2, num);
            if (x == num - 1) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Thuật toán này dựa trên định lý Miller để kiểm tra số nguyên tố. Nó được sử dụng để kiểm tra số nguyên tố lớn và nhanh hơn thuật toán Miller-Rabin trong một số trường hợp. Tuy nhiên, nó cũng không thực sự nhanh và tốn nhiều bộ nhớ.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Solovay-Strassen

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    for (int base : bases) {
        int x = jacobiSymbol(base, num);
        if (x == 0 || modularExponentiation(base, (num - 1) / 2, num) != x % num) {
            return false;
        }
    }
    return true;
}

private static int jacobiSymbol(int a, int b) {
    if (b <= 0 || b % 2 == 0) {
        return 0;
    }
    int j = 1;
    if (a < 0) {
        a = -a;
        if (b % 4 == 3) {
            j = -j;
        }
    }
    while (a != 0) {
        while (a % 2 == 0) {
            a /= 2;
            if (b % 8 == 3 || b % 8 == 5) {
                j = -j;
            }
        }
        int temp = a;
        a = b;
        b = temp;
        if (a % 4 == 3 && b % 4 == 3) {
            j = -j;
        }
        a %= b;
    }
    if (b == 1) {
        return j;
    }
    return 0;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Thuật toán Solovay-Strassen sử dụng định lý Jacobi và định lý Euler để kiểm tra số nguyên tố. Nó nhanh hơn AKS và đủ tốt để kiểm tra các số lớn.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Lucas-Lehmer

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int s = num - 1;
    while (s % 2 == 0) {
        s /= 2;
    }
    long m = (num - 1) / s;
    long v = 4;
    for (int i = 1; i < s; i++) {
        v = (v * v - 2) % num;
        if (v == 0) {
            return true;
        }
    }
    if (v != 0) {
        return false;
    }
    BigInteger p = BigInteger.valueOf(num);
    BigInteger q = BigInteger.valueOf(2).pow(s).multiply(BigInteger.valueOf(m)).add(BigInteger.ONE);
    for (int i = 0; i < 50; i++) {
        BigInteger a = BigInteger.valueOf((long) (Math.random() * (num - 2) + 2));
        BigInteger z = modularExponentiation(a, m, p);
        if (z.equals(BigInteger.ONE) || z.equals(p.subtract(BigInteger.ONE))) {
            continue;
        }
        boolean composite = true;
        for (int j = 0; j < s - 1; j++) {
            z = z.multiply(z).mod(p);
            if (z.equals(p.subtract(BigInteger.ONE))) {
                composite = false;
                break;
            }
        }
        if (composite) {
            return false;
        }
    }
    return true;
}

private static BigInteger modularExponentiation(BigInteger base, long exponent, BigInteger mod) {
    BigInteger result = BigInteger.ONE;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = result.multiply(base).mod(mod);
        }
        base = base.multiply(base).mod(mod);
        exponent /= 2;
    }
    return result;
}

Thuật toán Lucas-Lehmer được sử dụng để kiểm tra số nguyên tố Mersenne. Với những số nguyên tố Mersenne, đây là thuật toán nhanh nhất để kiểm tra tính nguyên tố của chúng. Tuy nhiên, nó chỉ áp dụng cho số nguyên tố Mersenne, không phải tất cả các số nguyên tố.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Frobenius

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int a = 2;
    while (jacobiSymbol(a, num) != -1) {
        a++;
    }
    int p = (int) (Math.pow(a, num - 1) % num);
    if (p != 1) {
        return false;
    }
    int q = (int) ((a * a - 4) % num);
    if (q < 0) {
        q += num;
    }
    q = (int) (Math.pow(q, (num - 1) / 2) % num);
    if (q != -1 && q != num - 1) {
        return false;
    }
    return true;
}

private static int jacobiSymbol(int a, int b) {
    if (b <= 0 || b % 2 == 0) {
        return 0;
    }
    int j = 1;
    if (a < 0) {
        a = -a;
        if (b % 4 == 3) {
            j = -j;
        }
    }
    while (a != 0) {
        while (a % 2 == 0) {
            a /= 2;
            if (b % 8 == 3 || b % 8 == 5) {
                j = -j;
            }
        }
        int temp = a;
        a = b;
        b = temp;
        if (a % 4 == 3 && b % 4 == 3) {
            j = -j;
        }
        a %= b;
    }
    if (b == 1) {
        return j;
    }
    return 0;
}

Thuật toán Frobenius sử dụng định lý Legendre và định lý Gauss để kiểm tra số nguyên tố. Nó là một thuật toán nhanh và dễ triển khai. Tuy nhiên, nó không hiệu quả bằng các thuật toán khác như Miller-Rabin và Solovay-Strasse

Kiểm tra số nguyên tố bằng cách sử dụng định lý Baille-PSW

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    if (isStrongPseudoprime(num)) {
        return true;
    }
    return false;
}

private static boolean isStrongPseudoprime(int num) {
    int s = 0;
    int d = num - 1;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    int[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    for (int base : bases) {
        if (base >= num) {
            break;
        }
        if (modularExponentiation(base, d, num) == 1) {
            continue;
        }
        boolean found = false;
        for (int i = 0; i < s; i++) {
            if (modularExponentiation(base, (int) (Math.pow(2, i) * d), num) == num - 1) {
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Thuật toán Baille-PSW được sử dụng để kiểm tra số nguyên tố và đặc biệt hiệu quả trong việc kiểm tra số nguyên tố lớn. Nó sử dụng kỹ thuật kiểm tra bất đẳng thức Legendre và kiểm tra bằng cách sử dụng những số nguyên tố nhỏ để kiểm tra.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Adleman-Pomerance-Rumely

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int a = 2;
    int d = 1;
    while (d == 1) {
        a++;
        d = gcd(a, num);
    }
    if (d != num) {
        return false;
    }
    int p = a;
    int q = modularExponentiation(p, (num - 1) / 2, num);
    if (q != 1 && q != num - 1) {
        return false;
    }
    int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
    for (int prime : primes) {
        if (num == prime) {
            return true;
        }
        if (modularExponentiation(prime, (num - 1) / 2, num) != legendreSymbol(prime, num)) {
            return false;
        }
    }
    return true;
}

private static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

private static int legendreSymbol(int a, int p) {
    return modularExponentiation(a, (p - 1) / 2, p);
}

Thuật toán Adleman-Pomerance-Rumely sử dụng định lý Legendre và định lý Gauss để kiểm tra số nguyên tố. Nó tương đối hiệu quả trong việc kiểm tra số nguyên tố lớn.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Baillie-PSW-Miller-Rabin

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    if (isStrongPseudoprime(num) && isMillerRabinProbablePrime(num)) {
        return true;
    }
    return false;
}

private static boolean isStrongPseudoprime(int num) {
    int s = 0;
    int d = num - 1;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    int[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    for (int base : bases) {
        if (base >= num) {
            break;
        }
        if (modularExponentiation(base, d, num) == 1) {
            continue;
        }
        boolean found = false;
        for (int i = 0; i < s; i++) {
            if (modularExponentiation(base, (int) (Math.pow(2, i) * d), num) == num - 1) {
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

private static boolean isMillerRabinProbablePrime(int num) {
    int[] bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    for (int base : bases) {
        if (base >= num) {
            break;
        }
        int r = num - 1;
        while (r % 2 == 0) {
            r /= 2;
        }
        int y = modularExponentiation(base, r, num);
        boolean isProbablePrime = y == 1;
        while (r != num - 1 && y != num - 1 && isProbablePrime) {
            y = (int) ((long) y * y % num);
            r *= 2;
            isProbablePrime = y != 1;
        }
        if (!isProbablePrime) {
            return false;
        }
    }
    return true;
}

private static int modularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

Thuật toán Baillie-PSW-Miller-Rabin kết hợp hai thuật toán kiểm tra số nguyên tố Baillie-PSW và Miller-Rabin để kiểm tra số nguyên tố. Đây là một thuật toán rất hiệu quả trong việc kiểm tra số nguyên tố lớn.

Kiểm tra số nguyên tố bằng cách sử dụng định lý AKS

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2 || num == 3) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int r = 2;
    while (r <= Math.sqrt(num)) {
        if (gcd(r, num) != 1) {
            return false;
        }
        int[] a = new int[num + 1];
        a[0] = 1;
        for (int i = 1; i <= num; i++) {
            a[i] = a[i - 1] * r % num;
        }
        for (int i = 1; i < num; i++) {
            if (a[i] == 1 && i != num - 1) {
                return false;
            }
        }
        r++;
    }
    return true;
}

private static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Thuật toán AKS (Agrawal-Kayal-Saxena) là một thuật toán mới được phát triển để kiểm tra số nguyên tố. Nó là một thuật toán hiệu quả và được coi là có thể chạy trên các số nguyên tố lớn. Tuy nhiên, thuật toán này có độ phức tạp cao và không hiệu quả trong việc kiểm tra các số nguyên tố nhỏ.

Kiểm tra số nguyên tố bằng cách sử dụng định lý Lucas-Lehmer

public static boolean isPrime(int p) {
    if (p <= 1) {
        return false;
    }
    if (p == 2) {
        return true;
    }
    if (p % 2 == 0) {
        return false;
    }
    int s = 4;
    int m = (int) Math.pow(2, (int) (Math.log(p + 1) / Math.log(2))) - 1;
    while (s <= m) {
        if (!isLucasLehmerPrime(p, s - 2)) {
            return false;
        }
        s *= 2;
    }
    return true;
}

private static boolean isLucasLehmerPrime(int p, int s) {
    long m = (long) Math.pow(2, p) - 1;
    long x = 4;
    for (int i = 0; i < s; i++) {
        x = (x * x - 2) % m;
    }
    return x == 0;
}

Thuật toán Lucas-Lehmer là một thuật toán rất hiệu quả để kiểm tra số nguyên tố Mersenne (số nguyên tố có dạng 2^p-1). Thuật toán này chỉ áp dụng cho các số nguyên tố Mersenne và không áp dụng cho các số nguyên tố khác.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *