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

Question

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

这是我的代码,但我不知道我是否已经正确地完成了它,因为我无法测试它,因为最小的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;
}

如果不正确,错误在哪里？

谢谢

应该防止PS溢出.

Answer 1

当你说"这是我的代码,但我不知道我是否做得正确或因为我无法测试它,因为最小的Carmichael数字是560,这对我的电脑来说太大了",那么结论是 - 你还没有正确完成.你应该能够在很短的一秒钟内处理561(560必须是一个错字).即使你的算法原则上是正确的,如果它无法处理最小的Carmichael数,那么它就没用了.

n是卡迈克尔,当且仅当它是复合材料,并且对于所有a与1 < a < n它们相对素n,同余a^(n-1) = 1 (mod n)成立.要直接使用此定义,您需要:

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

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

对于第一个 - 使用欧几里德算法得到最大公约数.它在循环中最有效地计算,但也可以通过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.相反 - 通过平方使用取幂,n在中间阶段取余数(mod ).它是一种基于观察的分而治之的算法,例如a^10 = (a^5)^2和a^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注意if n是复合,那么在a到达nwith的平方根之前必须至少有一个gcd(a,n) > 1.保持一个布尔标志,跟踪是否a遇到过这样的问题,如果超过平方根而没有找到这样的a,则返回0.对于那些a有gcd(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秒钟来运行并匹配此列表的初始部分.

这可能是一种实用的方法,用于检查数百万左右的数字是否是Carmichael数字.对于更大的数字,你可能应该得到一个很好的保理算法并使用Korseldt的标准,如维基百科条目中关于Carmichael数字所述.