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;
        
    }
    
}
nhatlonggunz viết 19:14 ngày 30/09/2018

Cám ơn bạn đã chia sẻ

Mai Anh Dũng viết 19:16 ngày 30/09/2018

Anh nghĩ là để chia sẻ thôi

Mình xin giới thiệu code mình có tham khảo từ daynhauhoc: viết theo mình hiểu.

nhatlonggunz viết 19:14 ngày 30/09/2018

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

rogp10 viết 19:18 ngày 30/09/2018

for(long long j=i;j*i<=maxn;j++)

Nên sửa thành:
for(long long j=i; j<=maxn; j+=i)

Bài liên quan
0