[Java] Tìm cách số nguyên tố trong Java

Chào các bạn, trong bài viết này, chúng ta sẽ cùng tìm hiểu về cách tìm số nguyên tố trong Java

Các ví dụ dưới dây sẽ in ra danh sách tất cả số nguyên tố từ 0 đến 1000:

Code:
2    3    5    7    11    13    17    19    23    29    31    37    41    43    47    53    59    61    67    71
73    79    83    89    97    101    103    107    109    113    127    131    137    139    149    151    157    163    167    173 
179    181    191    193    197    199    211    223    227    229    233    239    241    251    257    263    269    271    277    281 
283    293    307    311    313    317    331    337    347    349    353    359    367    373    379    383    389    397    401    409 
419    421    431    433    439    443    449    457    461    463    467    479    487    491    499    503    509    521    523    541 
547    557    563    569    571    577    587    593    599    601    607    613    617    619    631    641    643    647    653    659 
661    673    677    683    691    701    709    719    727    733    739    743    751    757    761    769    773    787    797    809 
811    821    823    827    829    839    853    857    859    863    877    881    883    887    907    911    919    929    937    941 
947    953    967    971    977    983    991    997 

Total: 168
3 ví dụ:
  • Java 8 Stream và BigInteger
  • Phiên bản trước Java 8
  • Giải thuật sàng Eratosthenes
1. Java 8 Stream và BigInteger
1.1 Sử dụng Stream.

PrintPrimeNumber.java
Java:
package com.mkyong.test;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class PrintPrimeNumber {

    public static void main(String[] args) {

        long count = Stream.iterate(0, n -> n + 1)
                .limit(1000)
                .filter(TestPrime::isPrime)
                .peek(x -> System.out.format("%s\t", x))
                .count();

        System.out.println("\nTotal: " + count);

    }

    public static boolean isPrime(int number) {

        if (number <= 1) return false; // 1 is not prime and also not composite

        return !IntStream.rangeClosed(2, number / 2).anyMatch(i -> number % i == 0);
    }

}
1.2 Sử dụng BigInteger::nextProbablePrime

Java:
    Stream.iterate(BigInteger.valueOf(2), BigInteger::nextProbablePrime)
            .limit(168)
            .forEach(x -> System.out.format("%s\t", x));

Hoặc BigInteger.TWO với

Java:
    Stream.iterate(BigInteger.TWO, BigInteger::nextProbablePrime)
            .limit(168)
            .forEach(x -> System.out.format("%s\t", x));

2. Trước Java 8
Không còn Java 8 Stream, trở về cơ bản.

PrintPrimeNumber2.java
Java:
package com.mkyong.test;

import java.util.ArrayList;
import java.util.List;

public class PrintPrimeNumber2 {

    public static void main(String[] args) {

        List<Integer> collect = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            if (isPrime(i)) {
                collect.add(i);
            }
        }

        for (Integer prime : collect) {
            System.out.format("%s\t", prime);
        }

        System.out.println("\nTotal: " + collect.size());

    }

    private static boolean isPrime(int number) {

        if (number <= 1) return false;    //  1 is not prime and also not composite

        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

}
3. Sàng số nguyên tố Eratosthenes
Giải thuật sàng Eratosthenes này thì tìm kiếm tất cả cả số nguyên tố rất nhanh.

Sieve_of_Eratosthenes_animation.gif
P.S Hình ở lấy từ Wikipedia

Ý tưởng giống thế này:
  • Vòng lặp 1# p = 2 = true, kế đến là 4, 6 ,8 ,10, 12, 14 … số cuối cùng, tất cả + 2 gán false
  • Vòng lặp 2# p = 3 = true, kế đến là 6 {false, 1#, bỏ qua}, 9, 12 {false, 1#, bỏ qua}, 15, 18 {false, 1#, bỏ qua}, 21… số cuối cùng, tất cả + 3 gán false
  • Vòng lặp 5# p = 6 = {false, 1#, bỏ qua}
  • Lặp… khi nào đến số cuối cùng và thực hiện giống như các bước trên
  • Tất cả các số = true là số nguyên tố
PrintPrimeNumber3
Java:
package com.mkyong.test;

import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;

public class PrintPrimeNumber3 {

    public static void main(String[] args) {

        List<Integer> result = primes_soe_array(1000);

        result.forEach(x -> System.out.format("%s\t", x));

        System.out.println("\nTotal: " + result.size());

    }

    /**
     * Sieve of Eratosthenes, true = prime number
     */
    private static List<Integer> primes_soe(int limit) {

        BitSet primes = new BitSet(limit);
        primes.set(0, false);                     
        primes.set(1, false);                     
        primes.set(2, limit, true);

        for (int p = 2; p * p <= limit; p++) {
            if (primes.get(p)) {
                for (int j = p * 2; j <= limit; j += p) {
                    primes.set(j, false);
                }
            }
        }

        List<Integer> result = new LinkedList<>();
        for (int i = 0; i <= limit; i++) {
            if (primes.get(i)) {
                result.add(i);
            }
        }

        return result;

    }

    // Some developers prefer array.
    public static List<Integer> primes_soe_array(int limit) {

        boolean primes[] = new boolean[limit + 1];
        Arrays.fill(primes, true);
        primes[0] = false;
        primes[1] = false;

        for (int p = 2; p * p <= limit; p++) {
            if (primes[p]) {
                for (int j = p * 2; j <= limit; j += p) {
                    primes[j] = false;
                }
            }
        }

        List<Integer> result = new LinkedList<>();
        for (int i = 0; i <= limit; i++) {
            if (primes[i]) {
                result.add(i);
            }
        }
        return result;
    }

}
Cần ai đó có thể giúp chuyển đổi thuật toán trên thành Java 8 Stream? ;)


Cám ơn các bạn đã theo dõi. Hẹn gặp lại các bạn trong các bài viết sau

Bài viết tham khảo tại: https://mkyong.com/java/java-prime-numbers-examples
 

Bình luận