Sàng nguyên tố và một số ứng dụng

Hôm nay chúng ta sẽ tìm hiểu sàng nguyên tố Sieve of Eratosthenes

ĐPT 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

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 phân tích ra thừa số ngyên tố:

nếu thay mảng dá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]

C code

#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