Tìm tất cả số nguyên tố nhỏ hơn hoặc bằng n

Đơn giản ta sẽ dò từ 2 đến n xem đó có phải nó số nguyên tố hay không và hàm tìm số nguyên tố như sau: 

public boolean isPrime(int n) {

if (n <= 1)

return false;

for (int i = 2; i < n; i++) {

if (n % i == 0)

return false;

}

return true;

}

Vấn đề sẽ xảy ra khi n là một số khoảng vài ngìn khi ta sẽ phải lặp rất nhiều để xem xét mà vấn đề chia hết cho 1 số ta có thể tái sử dụng được để tiết kiệm được thời gian. Tất nhiên phải tốn thêm bộ nhớ rồi :D

Sau đây là cách hiệu quả để làm việc đó (Phương pháp có tên Sieve of Eratosthenes)

Nguồn http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Phương pháp sieve of Eratosthenes là một trong những cách hiệu quả nhất cho việc tìm tất cả các số nguyên tố nhỏ hơn hoặc bàng n vói n nhỏ hơn khoảng 10 triệu (Ref Wiki).

Dưới đây là miêu tả giải thuật của phương pháp Eratosthenes:

1. Tạo một mảng liên tục từ 2 đến n: (2, 3, 4, …, n).
2. Coi p = 2 ( số nguyên tố đầu tiên).
3. Bắt đầu từ p ta sẽ đánh dấu mọi bội của p hư 2p,3p,4p,....
4. Tìm số tiếp theo x gần p nhất mà chưa bị đánh dấu, khi đó x sẽ là số nguyên tố, ta tiếp tục đánh dấu mọi bội của x và cứ thế cho đến hết mảng.

Khi giải thuật kết thúc thì tất cả các số không bị đánh dấu là số nguyên tố

Giải thích bằng ví dụ:
Giả sử n = 50. 

Tạo một mảng từ 2 đến 50

Ta sẽ đánh dấu tất cả bội của 2

Ta sẽ tìm được số 3 là số tiếp theo và đánh dấu mọi bội của 3.

Tương tự với số 5.

Khi kết thúc ta có mảng như sau

Các số nguên tố là: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Cài đặt:
Dưới đây là phàn code java giải thuật.

#include <stdio.h> #include <string.h>   public class SieveOfEratosthenes { // đánh dấu mọi bội của a ddeuf không phải là số nguyên tố public static void markMultiples(boolean[] arr, int a) { for (int i = 2 * a; i <= arr.length; i += a) { arr[i] = true; } } // A function to print all prime numbers smaller than n public static void SieveOfEratosthenes(int n) { // There are no prime numbers smaller than 2 if (n >= 2) { // Create an array of size n and initialize all elements as false boolean[] arr = new boolean[n + 1]; /* * Following property is maintained in the below for loop arr[i] == * false means i is prime arr[i] == true means i is not prime */ for (int i = 2; i <= n; ++i) { if (!arr[i]) { // (i) is prime, print it and mark its multiples System.out.println(i); markMultiples(arr, i); } } } } // Driver Program to test above function public static void main(String[] args) { int n = 30; System.out.printf("Following are the prime numbers below %d\n", n); SieveOfEratosthenes(n); } }

Output:

Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29

Có thể chạy thử tại đây http://ideone.com/fork/zCNaQt