本文共 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/