Cách tìm lũy thừa của một số nguyên tố (tối ưu)

#1

Mấy anh (chị) cho em ý tưởng về kiểm tra một số n có được viết dưới dạng n = a^b (với a là số nguyên tố, b > 1 thuộc N*)
Em viết được rồi nhưng trường hợp không tìm ra phải chạy hết vòng lập n lần, nhưng trong bài toán em đang làm giá trị lớn, phải duyệt từ 500.000 - 1.000.000.
Trung bình: 750.000*750.000 chạy rất lâu
Cảm ơn

#2

Mình cũng không rõ chính xác đáp án thế nào, nhưng search thấy mấy link này khá giống yêu cầu của bạn
http://diendantoanhoc.net/forum/index.php?/topic/1692-thuật-toán-aks/


3 Likes
#3

không biết useful không mà cảm ơn rất nhiều :smiley:

1 Like
#4

Hình như cái này là kiểm tra nó có phải là số nguyên tố hay không 1 cách nhanh nhất :frowning:

#5

Phương pháp của mình: vì n có cơ số a nhỏ nhất là 2. Nên b<= log2(n).

cho b chạy từ 2 đến log2(n):

  • a= căn bậc b của n.
  • kiểm tra n có phải là viết dưới dạng đề bài hay không.
  • kiểm tra a có phải là số nguyên tố hay không.

Độ phức tạp:

  • căn bậc n mất O(logn) (theo p.p newton)
  • kiểm tra b2 O(logn)
  • kiểm tra số nguyên tố O(logn)

=> dpt = O(log^2(n))

5 Likes
#6

Bạn giỏi quá thế mà không nghĩ ra, mặc dù không chạy ra liền nhưng cũng cải thiện phần nào

1 Like
#7

@Gio có hàm pow(n,1/b) = căn bậc b của n nên chỉ mất O(1) thôi.
Mà làm v có vẻ đơn giản hơn ko nhỉ ;:wink:
Ý tưởng tương tự như gió nhưng ngược lại và DPT time thì lâu hơn.

Nếu N chẵn thì sqrt(N) khi nào = 1.0 thì N có dạng 2^b; // có thể dùng mảng lưu trc các giá trị 2^b, nếu b nhỏ.
Còn ko thì thoát.
Dễ thấy số nguyên tố 99% là lẻ (trừ số 2). -> n phải lẻ nếu n ko thuộc dạng 2^b.
Nếu N lẻ thì
Tìm số nguyên tố nhỏ hơn sqrt(N); (dùng sàng eratosthenes)
do b>1 nên -> mọi số <=sqrt(N) bình phương lên đều nhỏ hơn hoặc bằng N

Sau khi lọc được mảng SNT < sqrt(n) thì cho 1 vòng for từ i= 3->sqrt(n);
nếu i là số nguyên tố thì kiểm tra

if( (double)(log_bậc_i(n)) - (int)(log_bậc_i(n)) == 0.0) thì n có dạng i ^(log_bậc_i(n))

log_bậc_i(n) được tính bằng CT: log(n)/log(i) với log() là log cơ số e tự nhiên. Dễ tìm thấy trong thư viện math.h
Độ phức tạp của thuật toán là O( sqrt(n)loglog( sqrt(n) ) );

3 Likes
#8 
bool snt(long n)
{
	if(n < 2)
		return false;
	if(n == 2 || n == 3)
		return true;
	for(int i = 2; i <= sqrt((float)n); i++)
		if(n % i == 0)
			return false;
	return true;
}

bool Check(long n, long &a, long &b)
{
	if(n < 4)
		return false;
	int m = (log((float)n))/(log((float)2));
	for(b = 2; b <= m; b++)
	{
		a = (int)pow((float)n, (float)1/b);
		if(snt(a))
			if(n == pow((float)a, b))
				return true;
		
	}
	return false;
}

Đây là em viết dựa trên ý tưởng của @Gio
nó chạy tầm 5s là ra, nhưng đề yêu cầu < 1s

Còn ý tưởng của @drgnz chưa hiểu rõ lắm, cảm phiền nói rõ 1 tí được không :smiley:

#9

Ta biết
n = a^b
-> log_a(n) = log_a(a^b) = b
Vì b là nguyên dương và lớn hơn 1, nên ta chỉ cần tìm b = log_a(n) sao cho b 1 số nguyên dương là đc :stuck_out_tongue:
-> vì b min = 2 -> cần duyệt sqrt(n) để tránh sót và vừa đủ, ko dư thừa.
1 vòng for chạy từ i = 3-> sqrt(n), với mỗi i, nếu i là số nguyên tố ta kiểm tra xem log_i(n) có phải là số nguyên hay ko. Nếu ko tiếp tục, nếu phải, thoát chương trình.
log_i() có CT tính ở trên.
Để kiểm tra chính xác có phải là log_a(n) là 1 số nguyên không, thì mình dùng cách này.

abs((double)log(n)/log(a) -round((double)log(n)/log(a))) == (double)0.0

Nếu muốn tối ưu hơn nữa.Bạn KT xem N có ở dạng a^2 không (chỉ mất O(1) thôi do có sàng + 1 câu if như trên). Rồi giảm xuống thành căn3 của N. Và duyệt đến căn3 của N thì sẽ tiết kiệm thêm đc nữa.

Bạn có thể tham khảo code của mình nhưng max n chỉ đc 10^12 th do giới hạng của mảng nguyên tố là 1m. ^^

2 Likes
#10

Tối ưu lại hàm check là dc mà.

typedef long long ll;
bool check(ll n, ll &a, ll &b){
ll t=4;
for(b=2;t<=n;t<<=1,b++){
 a=(ll) pow((double)n,1.0/(double)b);
 ll x=n;
 while(x%a==0) x/=a;
 if(x!=1) continue;
 if(snt(a)) return true;
}
return false;

}
2 Likes
#11

t<<=1 trong vòng lặp for có ý nghĩa gì vậy, Cảm ơn

#12

Là dịch trái 1 bit <=> t=t*2. Nhưng dịch bit sẽ nhanh hơn :smile:

#13

Có chạy từng bước cũng thấy nó t *= 2;
Ủa mà sao dịch 1 bit lại t *= 2 nhỉ, theo cách tính nào vậy

#14

Thời gian nó cũng same same nhau, tầm 2,5s - 3s

#15

Mấu chốt vẫn là hàm kt snt. Nếu dùng thuật toán Rabin-Miller sẽ chạy trong O(logn). Bạn tìm hiểu cách cài đặt trên wiki có nói rất rõ đấy :smiley:

1 Like
#16

Cách mình làm là : giả sử số nhập vào là int inputNumber

  1. tìm ra 1 dãy các số nguyên tố List myList từ 1 -> Sqrt(inputNumber)
  2. tìm trong dãy này số thỏa mãn đk inputNumber= a^b(a thuộc myList, b thuộc N*)
1 Like
#17

Ok, mình sẽ thử xem nó cải thiện không

1 Like
#18

Để mình xem thử nó có cải thiện thời gian không

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