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

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

Diễn đàn Toán học

Trang chủ

Trang chủ - Diễn đàn Toán học

AKS primality test

The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P". The algorithm was the first to determine whether any given number is prime or composite within polynomial time. The authors received the 2006 Gödel Prize an AK...

Algorithm for detecting prime powers

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

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

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

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

@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ỉ ;
Ý 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) ) );

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

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
-> 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. ^^

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

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;

}

t<<=1

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

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

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

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

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

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*)

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

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