Ошибка сегментации, когда массив превышает примерно 255000 int

Question

Я пишу программу, чтобы найти все простые числа меньше определенного числа.Как только мой список простых чисел становится выше примерно 255000 простых чисел, я получаю ошибку «Ошибка сегментации: 11».Монитор активности говорит, что мой процесс использует только 1,2 МБ.Вот мой код:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <unistd.h>

int main(){
    int N;
    int arraySize = 1;
    int *primes = malloc(100*sizeof(int));
    int isPrime = 1;
    primes[0] = 2;
    int timesRealloc = 0;
    int availableSlots = 100;

    printf("Please enter the largest number you want checked: \n");
    scanf("%d", &N);

    int j = 0;
    int i;
    for (i = 3; i <= N; i++){ 
        j = 0;
        isPrime = 1;
        while (primes[j] <= sqrt(i)) {
            if (i%primes[j] == 0) {
                isPrime = 0;
                break;
            }
            j++;
        }
        if (isPrime == 1){
            primes[arraySize] = i;
            arraySize++;
            availableSlots = availableSlots - 1;
        }
        if (availableSlots == 0){
            timesRealloc++;
            availableSlots = 100;
            primes = realloc(primes, 100*sizeof(int));
        }
    }

    /*
    for (i = 0; i < arraySize; i++){
        printf("%d\n", primes[i]);
    }
    */
    printf("process ID is %d\n", getpid());
    printf("I found %d primes\n", arraySize);
    printf("Memory was reallocated %d times\n", timesRealloc);
    printf("The largest prime I found was %d\n", primes[(arraySize-1)]);


    return 0;
}

Answer 1

Здесь есть две основные проблемы.

Во-первых, вы не перераспределяете столько места, сколько думаете.Вы делаете начальное распределение здесь:

int *primes = malloc(100*sizeof(int));

Затем перераспределите здесь:

primes = realloc(primes, 100*sizeof(int));

Количество пространства, которое вы перераспределяете, равно оригинальному размеру.Вы не делаете массив больше.Вы можете исправить это, отслеживая текущую емкость и увеличивая ее по мере необходимости.Таким образом, первоначальное распределение будет выглядеть следующим образом:

int capacity = 100;
int *primes = malloc(capacity*sizeof(int));

А перераспределение будет следующим:

timesRealloc++;
availableSlots = 100;
capacity += availableSlots;
primes = realloc(primes, capacity*sizeof(int));

Вторая проблема заключается в том, что вы начинаете arraySize с 1 и пишете в primes[arraySize], но availableSlots инициализируется до 100. Поэтому, когда вы достигаете текущей емкости, вы фактически записываете один элемент после конца.

Инициализируйте availableSlots до 99 вместо 10:

int availableSlots = 99;

Кроме того, не забудьте free(primes) в конце, чтобы не было утечки памяти.

Answer 2

Как было сказано в комментариях, вы выходите из массива простых чисел

Вот код с минимальным количеством модификаций для правильной работы:

#include <math.h>
#include <sys/types.h>
#include <unistd.h>

int main(){
    int N;
    int arraySize = 1;
    int *primes = malloc(100*sizeof(int));
    int isPrime = 1;
    primes[0] = 2;
    int timesRealloc = 0;
    int availableSlots = 100;

    printf("Please enter the largest number you want checked: \n");
    scanf("%d", &N);

    int j = 0;
    int i;
    for (i = 3; i <= N; i++){ 
        j = 0;
        isPrime = 1;
        while (primes[j] <= sqrt(i)) {
            if (i%primes[j] == 0) {
                isPrime = 0;
                break;
            }
            j++;
        }
        if (isPrime == 1){
            primes[arraySize] = i;
            arraySize++;
         /* LINE REMOVED */
        }
        if (arraySize == availableSlots){ /* MODIFIED */
            timesRealloc++;
            availableSlots += 100; /* MODIFIED */
            primes = realloc(primes, availableSlots*sizeof(int)); /* MODIFIED */
        }
    }

    /*
    for (i = 0; i < arraySize; i++){
        printf("%d\n", primes[i]);
    }
    */
    printf("process ID is %d\n", getpid());
    printf("I found %d primes\n", arraySize);
    printf("Memory was reallocated %d times\n", timesRealloc);
    printf("The largest prime I found was %d\n", primes[(arraySize-1)]);


    return 0;
}

Изменения обозначены комментарием

Для меня arraySize должен быть переименован как numberOfPrimes , а availableSlots должен быть переименован arraySize

---

Компиляция и выполнение:

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra p.c -lm
pi@raspberrypi:/tmp $ ./a.out
Please enter the largest number you want checked: 
500000
process ID is 6337
I found 41538 primes
Memory was reallocated 415 times
The largest prime I found was 499979

Исполнение в valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out
==6354== Memcheck, a memory error detector
==6354== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6354== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==6354== Command: ./a.out
==6354== 
1000
Please enter the largest number you want checked: 
process ID is 6354
I found 168 primes
Memory was reallocated 1 times
The largest prime I found was 997
==6354== 
==6354== HEAP SUMMARY:
==6354==     in use at exit: 800 bytes in 1 blocks
==6354==   total heap usage: 4 allocs, 3 frees, 3,248 bytes allocated
==6354== 
==6354== LEAK SUMMARY:
==6354==    definitely lost: 800 bytes in 1 blocks
==6354==    indirectly lost: 0 bytes in 0 blocks
==6354==      possibly lost: 0 bytes in 0 blocks
==6354==    still reachable: 0 bytes in 0 blocks
==6354==         suppressed: 0 bytes in 0 blocks
==6354== Rerun with --leak-check=full to see details of leaked memory
==6354== 
==6354== For counts of detected and suppressed errors, rerun with: -v
==6354== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

простых чисел должен быть свободным в конце, чтобы не было утечек памяти

---

Это просто деталь, но поведение не ожидается при вводе 1

pi@raspberrypi:/tmp $ ./a.out
Please enter the largest number you want checked: 
1
process ID is 6388
I found 1 primes
Memory was reallocated 0 times
The largest prime I found was 2

2 больше 1;-)

Это потому, что вы заставляете присутствие 2 (primes[0] = 2; и т. Д.)