30/09/2018, 17:09
Sàng nguyên tố(eratosthenes) và thừa số nguyên tố(factor)
Mình xin giới thiệu code mình có tham khảo từ daynhauhoc: viết theo mình hiểu.
sàng nguyên tố:
const long long maxn=1000000+5;
long long isPrime[maxn];
void Prime(){
for(long long i=2;i<=maxn;i++){
isPrime[i]=-1; // giả sử -1 thì i là số nguyên tố;
}
for(long long i=2;i<=maxn;i++){
if(isPrime[i]==-1)
for(long long j=i;j*i<=maxn;j++){
isPrime[j*i]=i; // lưu lại con số nguyên tố nhỏ nhất nó chia hết.
}
}
}
thừa số nguyên tố:
long long factor[1000];
void recrusive_factor(long long n,long long &fn){
if(isPrime[n]==-1){
factor[fn]=n;
fn++;
}else{
recrusive_factor(n/isPrime[n],fn);
factor[fn]=isPrime[n];
++fn;
}
}
Bài liên quan
Cám ơn bạn đã chia sẻ
Anh nghĩ là để chia sẻ thôi
Tại hồi trước em thấy có vài bạn cũng nói thế tới hồi em chép về run, chạy không được, vô hỏi lại thì mấy bạn lại bảo là đang hỏi.
Với lại thấy bạn không để trong mục nào cả, thêm với không có tag, nên em hỏi cho chắc ăn để mà move topic
Dù sao cũng xin lỗi bạn mình đọc không phân biệt được
Nên sửa thành:
for(long long j=i; j<=maxn; j+=i)