Cách phân tích một số thành thừa số nguyên tố nhanh

#1

mình đang viết chương trình phân tích một số thành thừa số nguyên tố và số mũ tương ứng.
VD:
10
2 1
5 1

#include<iostream> 
using namespace std; 
int main(){ 
	int i=2,x=0; 
	long long n;  
	cin >> n; 
	while(1){ 
		if(n%i==0){ 
			n=n/i;
			x++;
		} 
		else {
			if(x!=0) cout<<i<<" "<<x<<"\n";
			x=0;
			i++;
			if(n==1) break;
		} 
	} 
	return 0; 
}

cho mình hỏi là còn cách nào nhanh hơn không ạ??

#2

Dùng sàng Eratosthenes.

http://codeforces.com/blog/entry/7262

6 Likes
#3 
for (int i = 2; i <= n; i += 1)
{
	int c = 0;
	while (n % i == 0)
	{
		n /= i;
		c += 1;
	}
	if (c > 0)
		cout << i << " "<< c << endl;
}

Code này không chắc là nhanh hơn nhưng mà sáng sủa hơn code của bạn :joy:

Còn cách nhanh nhất đương nhiên là dùng sàng Eratosthenes, nhưng quá trình thiết lập sàng thì lâu, nên chỉ hiệu quả nếu thiết lập xong lưu thành file và dùng nhiều lần.

4 Likes
#4

k ổn b ạ . nó ra k đúng yêu cầu

#5

Mình đưa link đó cho bạn để bạn đọc rồi code lại và cải tiến chứ có phải là chép nguyên xi đâu @@

4 Likes
#6

Ra không đúng yêu cầu là thế nào? Mình đã test cẩn thận rồi đó :expressionless:

2 Likes
#7

không bạn ơi. đoạn code của bạn Trần Hoàn cơ bn ạ

1 Like
#8

à vẫn ra kết quả nhưng vẫn bị time limited bạn ạ

#9

Ồ, có bộ đo thời gian à. Nếu là web thì bạn cho mình link mình làm thử với.

2 Likes
#10

http://www.spoj.com/PTIT/status/ đây b ơi

#11

Đâu cần, tự khắc số chia sẽ nguyên tố :smiley: cái quan trọng hơn là i <= sqrt(n) :slight_smile:

2 Likes
#12

bạn nói rõ hơn được k??

#13

Mình giải thích ý 2 trước: Do nếu i chia hết n thì n/i chia hết n, nên ta thu được một cặp có số lớn số bé. Vậy khi i <= n/i thì i^2 <= n.
Ý 1: Sau bước lặp i=j, n không chia hết cho j (nếu có thì vẫn còn trong vòng while bên trong). Vậy theo quy nạp, n không chia hết cho 2…j, vậy nếu j+1 chia hết n thì j+1 không thể chia hết cho bất cứ số nào trong [2…j] được nữa (nếu có thì hóa ra là chưa chia cho hết?), theo định nghĩa của số nguyên tố :slight_smile:

Thực ra từ j (lẻ) có thể nhảy lên j+2 (cũng lẻ), hay dùng bước nhịp 2-4 luôn…

2 Likes
Phương pháp tối ưu để tìm số nguyên tố
#14

vậy bạn xem code này có chỗ nào chưa tối ưu không??

#include<iostream> 
using namespace std; 
int main(){ 
	int i=2,x=0; 
	long long n;  
	cin >> n; 
	while(1){ 
		if(n%i==0){ 
			n=n/i;
			x++;
		} 
		else {
			if(x!=0) cout<<i<<" "<<x<<"\n";
			x=0;
			if(i%2!=0) i=i+2;
			else i++;
			if(n==1) break;
		} 
	} 
	return 0; 
}
#15

Code này sẽ chia từ 1 đến n với số nguyên tố.

#16

Sàng nguyên tố Erathosenes nhanh nhất??? =))
Thuật toán này chỉ mạnh nếu cần phân tích nhiều số thôi :v
https://cp-algorithms.com/algebra/factorization.html
Floyd’s cycle-finding algorithm chỉ có căn bậc 4 log thôi

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?