Sàng nguyên tố Eratosthenes
Hôm nay chúng ta sẽ tìm hiểu sàng nguyên tố Sieve of Eratosthenes
Giới thiệu thuật toán
Độ phức tạp thuật toán
Độ phức tạp của thuật toán này là O(nloglogn)
Tư tưởng
Đánh dấu tất cả các số là bội của số nguyên tố p từ p^2 ->n
Demo code (python)
def sieve(n):
''' sàng nguyên tố [0,n] '''
danh_dau=[True]*(n+1) # giả sự lúc đầu đều có thể là snt
can_n=int(n**0.5)+1 # = floor(sqrt(n))+1
for i in range(2,can_n+1): # i= 2->can_n
if danh_dau[i]: # i là số nguyên tố
for j in range(i*i,n+1,i): # j=i*i, i*i+i , ...,n
danh_dau[j]=False ## j khong là số nguyên tố
primes=[]
for i in range(2,n+1): #i= 2->n
if danh_dau[i]: primes.append(i) #liệt kê lại số nguyên tố vào mảng mới
return primes
print sieve(100)
"""
#output:
[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]
"""
Ứng dụng
Dưới đây là ứng dụng của sàng số nguyên tố, trong bài toán phân tích ra thừa số nguyên tố.
Code dưới đây thay mảng đánh dấu không phải là [True|False] mà là mảng đánh dấu số nguyên tố trước đó
def gen_sieve_table(n):
''' sàng nguyên tố [0,n] '''
danh_dau=[0]*(n+1) # giả sự lúc đầu đều có thể là snt
can_n=int(n**0.5)+1 # = ceil(sqrt(n))+1
for i in range(2,can_n+1): # i= 2->can_n
if danh_dau[i]==0: # i là số nguyên tố -> giá trị =0 [không có ước nguyên tố nhỏ hơn #1]
for j in range(i*i,n+1,i): # j=i*i, i*i+i , ...,n
danh_dau[j]=i ## j khong là số nguyên tố
return danh_dau
def factor(n,sieve_table):
if sieve_table[n]==0: ## là số nguyên tố trả lại ước là chính nó
return [n]
else:
d=sieve_table[n] ## chứa 1 ước nguyên tố nhỏ nhất là d
return [d] + factor(n//d,sieve_table)
sieve_table=gen_sieve_table(100000)
print factor(12345,sieve_table)
output:
[5, 3, 823]
Demo code (C programming language)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 1000000
int a[maxn+1];
int primes[maxn],primes_len;
void sieve(){
int i,j;
memset(a,sizeof(int)*(maxn+1),0);
for(i=2;i*i<=maxn;++i){
if(a[i]) continue; //i la hop so
for(j=i*i; j<=maxn;j+=i){ // cac so la boi cua i tu i*i ->n
a[j]=i; // cai nay luu lai so nguyen to nho nhat ma j chia het cho i
}
}
/// liet ke lai so nguyen to
primes[0]=2;
primes_len=1;
for(i=3;i<=maxn;i+=2){
if(a[i]) continue;
primes[primes_len]=i;
primes_len++;
}
}
int ft[50],fn;
void recrusive_factor(int n){
if(!a[n]){
ft[fn]=n;
fn++;
}else{
recrusive_factor(n/a[n]);
ft[fn]=a[n];
++fn;
}
}
void factor(int n){
fn=0;
recrusive_factor(n);
}
int main() {
sieve();
printf("so luong so nguyen to <= (%d) = %d\n",maxn,primes_len);
int n=12345;
printf("phan tich thua so nguyen to %d=",n);
factor(n);
int i;
for(i=0;i<fn-1;++i){
printf("%d*",ft[i]);
}
printf("%d\n",ft[fn-1]);
return 0;
}
output:
so luong so nguyen to <= (1000000) = 78498
phan tich thua so nguyen to 12345=823*3*5
khắc phục được nhược điểm sử dụng quá nhiều mem bằng cách chỉ sử dụng một vùng nhớ nhỏ hơn kích thước của mem (OS) page và tốc độ cũng cao hơn.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?