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

Dùng sàng Eratosthenes.

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

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

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.

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

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 @@

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

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

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

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

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

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

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

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?), đây là định nghĩa của số nguyên tố

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…

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; 
}