Đơ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:
Cài đặt:
Dưới đây là phàn code java giải thuật.
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:
- Tạo một mảng liên tục từ 2 đến n: (2, 3, 4, …, n).
- Coi p = 2 ( số nguyên tố đầu tiên).
- Bắt đầu từ p ta sẽ đánh dấu mọi bội của p hư 2p,3p,4p,....
- 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.
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
