Bài viết này sẽ cung cấp cho bạn một cái nhìn toàn diện về các thuật toán khác nhau để tìm tất cả các số nguyên tố nhỏ hơn một số N cho trước. Chúng ta sẽ khám phá các phương pháp khác nhau, từ cách tiếp cận đơn giản, dễ hiểu đến các thuật toán hiệu quả hơn như sàng Eratosthenes. Bạn sẽ tìm thấy các đoạn code mẫu được viết bằng nhiều ngôn ngữ lập trình phổ biến, bao gồm R, C++, Java, Python, C#, PHP và Javascript, giúp bạn dễ dàng triển khai và thử nghiệm.
Số nguyên tố là những viên gạch cơ bản của số học. Chúng chỉ chia hết cho 1 và chính nó. Việc tìm kiếm và nghiên cứu các số nguyên tố có vai trò quan trọng trong nhiều lĩnh vực của khoa học máy tính và toán học, bao gồm:
Nắm vững các thuật toán tìm kiếm số nguyên tố không chỉ giúp bạn giải quyết các bài toán lập trình mà còn cung cấp cho bạn những kiến thức nền tảng vững chắc về toán học và khoa học máy tính.
Phương pháp đơn giản nhất để kiểm tra xem một số `n` có phải là nguyên tố hay không là duyệt qua tất cả các số từ 2 đến `n-1` và kiểm tra xem `n` có chia hết cho số nào trong số đó hay không. Nếu `n` chia hết cho bất kỳ số nào, thì nó không phải là nguyên tố. Ngược lại, nếu nó không chia hết cho bất kỳ số nào, thì nó là nguyên tố.
Tuy nhiên, phương pháp này khá chậm, đặc biệt đối với các số lớn. Độ phức tạp thời gian của nó là O(N).
Một cải tiến đáng kể là chỉ kiểm tra các ước số từ 2 đến căn bậc hai của `n`. Nếu một số `n` không phải là nguyên tố, nó phải có ít nhất một ước số nhỏ hơn hoặc bằng căn bậc hai của nó. Vì vậy, chúng ta có thể giảm số lượng phép chia cần thực hiện.
Độ phức tạp thời gian của thuật toán này là O(√N), tốt hơn nhiều so với phương pháp ngây thơ.
Sàng Eratosthenes là một thuật toán cổ điển và hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn một số `N` cho trước. Thuật toán hoạt động bằng cách đánh dấu tất cả các bội số của các số nguyên tố là hợp số (không phải nguyên tố), bắt đầu từ 2. Sau khi hoàn thành, tất cả các số còn lại chưa được đánh dấu là số nguyên tố.
Các bước thực hiện thuật toán:
Độ phức tạp thời gian của sàng Eratosthenes là O(N * log(log(N))), một trong những thuật toán nhanh nhất để tìm số nguyên tố trong một phạm vi nhất định.
Dưới đây là các đoạn code mẫu cho thuật toán sàng Eratosthenes được viết bằng nhiều ngôn ngữ lập trình:
find_primes <- function(n) {
if (n < 2) {
return(integer(0))
}
primes <- rep(TRUE, n + 1)
primes[1] <- FALSE
primes[2] <- TRUE
for (i in 2:sqrt(n)) {
if (primes[i]) {
for (j in (i*i):(n+1) by = i) {
primes[j] <- FALSE
}
}
}
which(primes) - 1
}
# Example usage
n <- 50
prime_numbers <- find_primes(n)
print(prime_numbers)
#include
#include
using namespace std;
vector findPrimes(int n) {
vector primes(n + 1, true);
primes[0] = primes[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (primes[p]) {
for (int i = p * p; i <= n; i += p)
primes[i] = false;
}
}
vector result;
for (int p = 2; p <= n; ++p) {
if (primes[p])
result.push_back(p);
}
return result;
}
int main() {
int n = 50;
vector primeNumbers = findPrimes(n);
for (int prime : primeNumbers) {
cout << prime << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class PrimeFinder {
public static List findPrimes(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++) {
primes[i] = true;
}
primes[0] = primes[1] = false;
for (int p = 2; p * p <= n; p++) {
if (primes[p]) {
for (int i = p * p; i <= n; i += p)
primes[i] = false;
}
}
List result = new ArrayList<>();
for (int p = 2; p <= n; p++) {
if (primes[p])
result.add(p);
}
return result;
}
public static void main(String[] args) {
int n = 50;
List primeNumbers = findPrimes(n);
for (int prime : primeNumbers) {
System.out.print(prime + " ");
}
System.out.println();
}
}
def find_primes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for p in range(2, int(n**0.5) + 1):
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
return [p for p in range(2, n + 1) if primes[p]]
# Example usage
n = 50
prime_numbers = find_primes(n)
print(prime_numbers)
using System;
using System.Collections.Generic;
public class PrimeFinder {
public static List FindPrimes(int n) {
bool[] primes = new bool[n + 1];
for (int i = 0; i <= n; i++) {
primes[i] = true;
}
primes[0] = primes[1] = false;
for (int p = 2; p * p <= n; p++) {
if (primes[p]) {
for (int i = p * p; i <= n; i += p)
primes[i] = false;
}
}
List result = new List();
for (int p = 2; p <= n; p++) {
if (primes[p])
result.Add(p);
}
return result;
}
public static void Main(string[] args) {
int n = 50;
List primeNumbers = FindPrimes(n);
foreach (int prime in primeNumbers) {
Console.Write(prime + " ");
}
Console.WriteLine();
}
}
function findPrimes(n) {
let primes = new Array(n + 1).fill(true);
primes[0] = primes[1] = false;
for (let p = 2; p * p <= n; p++) {
if (primes[p]) {
for (let i = p * p; i <= n; i += p)
primes[i] = false;
}
}
let result = [];
for (let p = 2; p <= n; p++) {
if (primes[p])
result.push(p);
}
return result;
}
// Example usage
let n = 50;
let primeNumbers = findPrimes(n);
console.log(primeNumbers.join(" "));
Việc tìm số nguyên tố nhỏ hơn N là một bài toán cơ bản trong khoa học máy tính với nhiều ứng dụng thực tế. Bằng cách hiểu các thuật toán khác nhau và độ phức tạp của chúng, bạn có thể chọn phương pháp phù hợp nhất cho nhu cầu của mình. Hy vọng rằng bài viết này đã cung cấp cho bạn một nền tảng vững chắc để khám phá thế giới thú vị của số nguyên tố.
Bài viết liên quan