Cの素数ファインダ

Question

私の素数ファインダは、数値が素数かどうかを調べるために、平方根までの素数を調べるだけです。したがって、0とxの間のすべての素数を見つけるには、0とxの平方根の間のすべての素数を知ることで、非常に素早く計算することができます。 brute forceメソッドを使って見つかったプライマリファインダの最初のリスト。次に、このリストをクイックプライムファインダに渡します。

このコードは正しくコンパイルされ、正常に動作しますが、何らかの理由で5百万以上の上限を試してみるとセグメント分割エラー11が発生します。私が "finalPrimes"のリストを作ろうとするまで、それは "すべて良い"ようです。なぜこれが/一般的なフィードバックであるかもしれないかに関するどんな考えも非常に認められます。 PS、私はCの新しいので、私のデザインに関する一般的な解説も高く評価されています。

#include<stdio.h> 
#include<math.h> 
#include<stdbool.h> 

void fill_array_with_primes_brute(int *array, int upper); 

void fill_array_with_primes_quick(int *initial, int *final, int lower, int upper); 

int find_end(int *array, int length); 

bool is_prime_brute(int num); 

bool is_prime_quick(int *primes, int num); 



int main(void) 
{ 
    int upperBound; 
    printf("Enter upper bound: \n"); 
    scanf("%i", &upperBound);        /* get user input for upper bound */ 
    int boundRoot = (int) sqrtf((float) upperBound) + 1; /* get the root of this upper bound for later use */ 
    printf("%i is root\n", boundRoot); 
    printf("All good\n"); 
    int initialPrimes[boundRoot/2];      /* we can safely assume that the number of primes between 0 and x is less than x/2 for larger numbers */ 
    printf("All good\n"); 
    int finalPrimes[upperBound/2]; 
    printf("All good\n"); 
    fill_array_with_primes_brute(initialPrimes, boundRoot); 
    printf("All good\n"); 
    int initialPrimesSize = find_end(initialPrimes, sizeof initialPrimes/sizeof initialPrimes[0]); 
    printf("All good\n"); 
    printf("%i primes between 0 and %i\n", initialPrimesSize, boundRoot); 
    printf("All good\n"); 
    initialPrimes[initialPrimesSize] = 50000; 
    printf("All good\n"); 
    printf("\nHere they are: \n");    /* This will act as a barrier between the primes and the trailing 0's so that is_prime_quick works properly */ 
    for (int x = 0; x < initialPrimesSize; x++) 
    { 
    printf("%i\n", initialPrimes[x]); 
    } 
    fill_array_with_primes_quick(initialPrimes, finalPrimes, boundRoot, upperBound); 
    printf("\nHere are the other ones: \n"); 
    int pos = 0; 
    while (finalPrimes[pos] != 0) 
    { 
    printf("%i\n", finalPrimes[pos]); 
    pos++; 
    } 
} 

void fill_array_with_primes_brute(int *array, int upper)  /* upper is the number up to which we want primes */ 
{ 
    array[0] = 2; 
    array[1] = 3;         /* fill array with 2 & 3 cos yolo */ 
    int arrayCount = 2;        /* start this counter cos C doesn't have ArrayLists */ 
    for (int pote = 4; pote < upper; pote++)   /* every number in range is potentially a prime */ 
    { 
    if (is_prime_brute(pote)) 
    { 
     array[arrayCount] = pote; 
     arrayCount++; 
    } 
    } 
} 

bool is_prime_brute(int num) 
{ 
    for (int x = 2; x < (int) sqrtf((float) num) + 1; x++) /* go through numbers up to the number's square root looking for a factor */ 
    { 
    if (num % x == 0) 
    { 
     return false;        /* has a factor, so not a prime */ 
    } 
    } 
    return true;          /* if we've made it this far it's a prime */ 
} 

void fill_array_with_primes_quick(int *initial, int *final, int lower, int upper) 
{ 
    int arrayCount = 0; 
    for (int pote = lower; pote < upper; pote++) 
    { 
    if (is_prime_quick(initial, pote)) 
    { 
     final[arrayCount] = pote; 
     arrayCount++; 
    } 
    } 
} 

bool is_prime_quick(int *primes, int num) 
{ 
    int pos = 0; 
    while (primes[pos] < (int) sqrtf((float) num) + 1)  /* while the number we're at in the array is less than the number's square root */ 
    { 
     if (num % primes[pos] == 0) 
     { 
     return false; 
     } 
     pos++; 
    } 
    return true; 
} 

int find_end(int *array, int length)    /* Find the true end of the array, as it will contain a few trailing 0's */ 
{ 
    for(int x = 0; x < length; x++) 
    { 
    if (array[x] == 0) 
    { 
     return x; 
    } 
    } 
    return 0; 
} 

Answer 1

これは、自動メモリ領域（「スタック上」とも呼ばれます）にあまりに多くのメモリを割り当てるために発生します。

malloc秒でこれらの宣言を置き換え：

int initialPrimes[boundRoot/2]; 
int finalPrimes[boundRoot/2]; 

は

int *initialPrimes = malloc(sizeof(int)*boundRoot/2); 
int *finalPrimes = malloc(sizeof(int)*boundRoot/2); 

またboundRoot/2でsizeof initialPrimes/sizeof initialPrimes[0])式を置き換えるになります。また、両方の割り当てアレイに対してfreeへの呼び出しを追加：mainにおける最終whileループの後、

free(initialPrimes); 
free(finalPrimes); 

Answer 2

を追加する5メートルの平方根が約2236であるので、スタックオーバーフローです。あなたのコードは、しかし安全であるように思われるので、セグメンテーションフォールトは、任意の未定義の動作が原因ではありません。

Enter upper bound: 
5000000 
2237 is root 
All good 
All good 
ASAN:DEADLYSIGNAL 
================================================================= 
==24998==ERROR: AddressSanitizer: stack-overflow on address 0x7ffe01f4fb28 (pc 0x55d6add011dd bp 0x7ffe028da410 sp 0x7ffe01f4fb30 T0) 
    #0 0x55d6add011dc in main (/tmp/a.out+0x11dc) 
    #1 0x7fbb442fb4c9 in __libc_start_main (/usr/lib/libc.so.6+0x204c9) 
    #2 0x55d6add00d19 in _start (/tmp/a.out+0xd19) 

SUMMARY: AddressSanitizer: stack-overflow (/tmp/a.out+0x11dc) in main 
==24998==ABORTING 

@dasblinkenlightが述べたように、あなたはヒープ割り当てを使用して、それを修正することがあります。しかし、primality test algorithmのいずれかを考えてみましょう。これは高速でスケーラブルですが、実際には暗号に使用されているものが100％正しいとは証明されていません。

Answer 3

ここでは、自動可変長配列を宣言して定義すると、クラッシュが発生します：int finalPrimes[upperBound/2];。

1. VLAはスタック上にあり、スタックスペースは比較的小さい。

問題を解決するには、mallocを使用して手動でヒープに領域を割り当てる必要があります。

int* initialPrimes = malloc(sizeof(int)*(upperBound/2));      
int* finalPrimes = malloc(sizeof(int)*(upperBound/2)); 

、あなたは彼らと一緒に行われたときに、メモリをfreeすることを忘れないでください。

配列をグローバル変数として宣言した場合（ある一定の大きなサイズで）、コンパイラはそれらを割り当てます。例えば

される次の宣言は、クラッシュワニスます

int finalPrimes[5000001]; 
int initialPrimes[5000001]; 
int main(void){ 
    ....