本文共 1397 字，大约阅读时间需要 4 分钟。
费马素数测试（Fermat Primality Test）是一种广泛应用于判断数是否为素数的概率化算法。以下将展示一个用Objective-C语言实现的费马素数测试算法的完整代码示例。
费马素数测试基于以下数学原理：对于一个奇数p，如果p-1不能被任何数整除，则p可能是素数。具体来说，对于给定的数n，我们选择一个基数a，并计算a^(p-1) mod p。如果结果不等于1，则n是合数；否则，n可能是素数。
以下是Objective-C代码实现：
#import@interface FermatPrimalityTest : NSObject- (BOOL)isPrime:(NSInteger)n withTests:(NSInteger)t;@end@implementation FermatPrimalityTest- (BOOL)isPrime:(NSInteger)n withTests:(NSInteger)t{ // 选择基数a NSInteger a = rand() % n + 1; // 计算a^(p-1) mod p NSInteger result = modpow(a, n - 1, n); if (result != 1) { return NO; } // 进行t次测试 for (NSInteger i = 0; i < t; i++) { a = rand() % n + 1; result = modpow(a, n - 1, n); if (result != 1) { return NO; } } return YES;}// 计算 (base^exp) mod modnum- (NSInteger)modpow:(NSInteger)base exp:(NSInteger)exp mod:(NSInteger)modnum{ NSInteger result = 1; base = base % modnum; while (exp > 0) { if (exp % 2 == 1) { result = (result * base) % modnum; } base = (base * base) % modnum; exp /= 2; } return result;}
通过上述代码，我们可以有效地判断一个数是否为素数。该算法基于费马素数测试原理，结合了快速幂算法和随机化选择基数的方法，确保了高效性和准确性。
转载地址：http://lsnfk.baihongyu.com/