gpt4 book ai didi

c - 找到给定区间 [a,b) - C 中的所有 Carmichael 数

转载 作者:行者123 更新时间:2023-12-04 10:44:05 24 4
gpt4 key购买 nike

我正在使用具有不同功能的数学软件,其中之一是在给定区间 [a,b) 中找到所有 Carmichael 数

这是我的代码,但我不知道我是否正确地完成了它,因为我无法测试它,因为最小的 Carmichael 数字是 560,这对我的电脑来说太大了,无法处理。

#include <stdio.h>

int main() {

unsigned int begin, end;

printf("Write an int (begin):\n");
scanf("%d", &begin);

printf("Write an int (end):\n");
scanf("%d", &end);

int i;

for( int i=begin; i<end; i++ ) {

long unsigned int a_nr = i-1;

int a[a_nr];

for( int j=0; j<a_nr; j++ ) {
a[j] = j;
}

unsigned long c_nr[a_nr];

for( int k=0; k<a_nr; k++ ) {
unsigned long current_c_nr;
int mod;
for( int l=0; l<i; l++ ) {
current_c_nr= current_c_nr * a[k];
}
mod = current_c_nr%i;
if( mod==a[k] && mod!=a[k] ) {
c_nr[k] = i;
}

}

}

return 0;
}

如果不对,错在哪里?

谢谢

应防止 P.S 溢出。

最佳答案

当你说“这是我的代码,但我不知道我是否正确地完成了它,因为我无法测试它,因为最小的 Carmichael 数字是 560,这对我的电脑来说太大了,无法处理”那么结论是——你没有做对。您应该能够在几分之一秒内处理 561(560 一定是打字错误)。即使您的算法原则上是正确的,但如果它不能处理最小的 Carmichael 数,那么它也是无用的。

n是 Carmichael 当且仅当它是复合的并且对于所有 a1 < a < nn 相对质数, 全等 a^(n-1) = 1 (mod n)持有。要直接使用此定义,您需要:

1) 一种测试 a 是否有效的方法和 n是相对质数

2) 计算a^(n-1) (mod n)的有效方法

对于第一个 -- 使用 Euclidean algorithm对于最大公约数。它在循环中计算最有效,但也可以通过简单的递归 gcd(a,b) = gcd(b,a%b) 来定义。有依据gcd(a,0) = a .在 C 中,这只是:

unsigned int gcd(unsigned int a, unsigned int b){
return b == 0? a : gcd(b, a%b);
}

关于第二点——在计算 a^k (mod n) 时几乎是你能做的最糟糕的事情是先计算a^k通过重复乘法,然后将结果修改为 n .相反——使用 exponentiation by squaring ,在中间阶段取余数 (mod n)。它是一种基于观察的分而治之算法,例如a^10 = (a^5)^2a^11 = (a^5)^2 * a .一个简单的 C 实现是:

unsigned int modexp(unsigned int a, unsigned int p, unsigned int n){
unsigned long long b;
switch(p){
case 0:
return 1;
case 1:
return a%n;
default:
b = modexp(a,p/2,n);
b = (b*b) % n;
if(p%2 == 1) b = (b*a) % n;
return b;
}
}

注意 unsigned long long 的使用在计算 b*b 时防止溢出.

测试是否n是Carmichael,你不妨先测试一下是否n是偶数并返回 0在这种情况下。否则,遍历数字,a , 在 2 范围内至 n-1 .首先检查是否 gcd(a,n) == 1请注意,如果 n是复合的那么你必须至少有一个a在你达到 n 的平方根之前与 gcd(a,n) > 1 ).保留一个 bool 标志,用于跟踪是否有 a已经遇到了,如果你超过了平方根却没有找到这样一个 a , 返回 0 .对于那些agcd(a,n) == 1 , 计算模幂 a^(n-1) (mod n) .如果这与 1 不同,则返回 0 .如果您的循环完成检查所有 a下面n不回0 , 那么这个数就是Carmichael,所以返回1。一个实现是:

int is_carmichael(unsigned int n){
int a,s;
int factor_found = 0;
if (n%2 == 0) return 0;
//else:
s = sqrt(n);
a = 2;
while(a < n){
if(a > s && !factor_found){
return 0;
}
if(gcd(a,n) > 1){
factor_found = 1;
}
else{
if(modexp(a,n-1,n) != 1){
return 0;
}
}
a++;
}
return 1; //anything that survives to here is a carmichael
}

一个简单的驱动程序:

int main(void){
unsigned int n;
for(n = 2; n < 100000; n ++){
if(is_carmichael(n)) printf("%u\n",n);
}
return 0;
}

输出:

C:\Programs>gcc carmichael.c

C:\Programs>a
561
1105
1729
2465
2821
6601
8911
10585
15841
29341
41041
46657
52633
62745
63973
75361

这只需要大约 2 秒的时间来运行并匹配 this 的初始部分列表。

这可能是一种比较实用的方法,用于检查一百万左右的数字是否是卡迈克尔数字。对于更大的数字,您可能应该为自己准备一个好的因式分解算法并使用 Wikipedia entry 中描述的 Korseldt 准则。在 Carmichael 数上。

关于c - 找到给定区间 [a,b) - C 中的所有 Carmichael 数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33426414/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com