所以很明显，数字 399137 本身并不会导致分段错误，但我的程序在相同的计算中始终崩溃。它计算从 2 到给定限制（默认 1,000,000）的 Euler 的 totient（ phi 函数）的值。它通过从先前计算的欧拉总值中保留一个线性排序的素数列表来做到这一点。当尝试将第 33791 个素数 (339137) 添加到素数列表时，会导致分段错误。注意内存在这个计算中没有重新分配。我尝试使用gdb来定位问题，它指向了将素数添加到列表中的行（见下文）。
为了存储低于 100 万的所有素数，我的程序将动态分配8192*10*4字节(320KB)。对我来说，需要那么多连续的内存似乎没有问题。
那么为什么我的程序在尝试将 339137 添加到素数列表时总是出现分段错误？这种分段错误的原因是什么？
C Code:
#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
uint32_t phi (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t gcd_bin (uint32_t u, uint32_t v);
uint32_t isPrime (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
void addPrime (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t isInArr (uint32_t n, uint32_t *primes, uint32_t count);
uint32_t expand_arr(uint32_t **arr, uint32_t *size);
void print_arr (uint32_t *arr, uint32_t count);
uint32_t print_help(char* str);
int main(int argc, char* argv[]) {
uint32_t z=1000000; //default
uint32_t count=0,size = 10; //default
uint32_t i,n;
// uint32_t x,y; //max numerator & denominator of ratio
uint32_t *primes = malloc(size * sizeof(uint32_t));
if(argc > 1 && !strcmp(argv[1],"--help")) { return print_help(argv[0]); }
if(argc > 1) { sscanf(argv[1],"%u",&z); }
uint32_t old=size;
for(i=2,/*x=y=1,*/count=0; i<=z; ++i) {
n = phi(i,primes,&count,&size);
fprintf(stderr,"\ni=%u phi(i)=%u\t: c=%u s=%u ",i,n,count,size);
}
// printf("%u/%u\n",x,y);
return 0;
}
uint32_t phi(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
uint32_t i,bound;
// Base case
if(n < 2)
return 0;
// Is Prime? (Lehmer's conjecture)
if(isPrime(n,primes,count,size))
return n-1;
// Even number?
if((n & 1) == 0 ) {
int m = n >> 1;
return ~m & 1 ? phi(m,primes,count,size)<<1 : phi(m,primes,count,size);
}
// Find (smallest) prime factor using list of primes
for(i=0,bound=(uint32_t)sqrt(n); primes[i] < bound && i<*count && (n%primes[i])!=0; ++i);
uint32_t m = primes[i];
uint32_t o = n/m;
uint32_t d = gcd_bin(m, o);
return d==1 ? phi(m,primes,count,size)*phi(o,primes,count,size)
: phi(m,primes,count,size)*phi(o,primes,count,size)*(d/phi(d,primes,count,size));
}
uint32_t isPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
uint32_t i,prime,bound;
for(i=0,prime=1,bound=(uint32_t)sqrt(n)+1; prime && i<*count && primes[i]<=bound; ++i)
prime = n%primes[i];
if(prime)
addPrime(n,primes,count,size);
return prime;
}
void addPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
if(*count >= *size) {
if(!expand_arr(&primes,size)) {
fprintf(stderr,"dying gracefully!");
exit(1); //realloc failure
}
}
if(!isInArr(n,primes,*count))
primes[(*count)++] = n; /* ERROR IS HERE APPARENTLY */
}
uint32_t expand_arr(uint32_t **primes, uint32_t *size) {
*size *= 2;
*primes = realloc(*primes, *size * sizeof(uint32_t));
return *primes!=NULL;
}
uint32_t isInArr(uint32_t n, uint32_t *primes, uint32_t count) {
uint32_t hi,low,mid,val;
low = 0; hi = count; // set bounds
while(low < hi) { // binary search
mid = low/2 + hi/2;
val = primes[mid];
if(val == n) return 1;
if(val > n) hi = mid;
if(val < n) low = mid+1;
}
return 0;
}
void print_arr(uint32_t *arr, uint32_t count) {
uint32_t i;
for(i=0; i<count; ++i)
printf("%u,",arr[i]);
printf("\n");
}
uint32_t gcd_bin(uint32_t u, uint32_t v) {
/* simple cases (termination) */
if(u == v) return u;
if(u == 0) return v;
if(v == 0) return u;
/* look for even numbers */
if( ~u & 1) {
if(v & 1) return gcd_bin(u >> 1, v); /* u is even, v is odd */
else return gcd_bin(u >> 1, v >> 1) << 1; /* u is even, v is even */
}
if( ~v & 1) return gcd_bin(u, v >> 1); /* u is odd, v is even */
/* reduce larger argument */ /* u is odd, v is odd */
return (u > v) ? gcd_bin((u - v) >> 1, v)
: gcd_bin((v - u) >> 1, u);
}
uint32_t print_help(char* str) {
printf(" Usage: %s <limit> \n",str);
printf(" Calculates the values of euler's totient (phi fnction) \n");
printf(" from 2 to <limit> inclusively\n");
printf(" * limit : a decimal number\n");
printf(" : default = 1000000\n");
return 0;
}