Certain numbers cause free() to segmentation fault in Sieve of Eratosthenes algorithm

Question

My problem is this code runs fine most of the time, but if I enter certain values of n (some that I have found are 1000 and 111) it gives me a SIGSEGV error (I think that is how you say that). I found that the error would happen when free is called on marks, so I ran valgrind on the program using n = 1000, but I am not sure what to make of it, or how to solve this error. I'm really looking for answers on how to solve this bug, not necessarily on the algorithm itself, but it is supposed to be an implementation of the Sieve of Eratosthenes. Thanks everyone.
Code:

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


    int *eSieve(int n) 
    {
        /*first number of the array is the number of primes*/
        int i = 0;
        int *num = 0;
        int *marks = 0;
        int *primes = 0;
        int k = 1;
        int m = 0;
        int j = 0;
        int nPrimes = 0;

        num = malloc(sizeof(int) * n);
        marks = malloc(sizeof(int) * n);

        for (i = 0;i < n;i++) {
            num[i] = i + 1;
            marks[i] = 0;
        } 

        marks[0] = 2; /*mark 1 as special */
        i = 1;
        /*1 is prime, 2 is composit*/
        while (k <= (int) sqrt(n)) {
            if (marks[k] == 0) {
                m = num[k]; 
                for (i = 2; j < n; i++) {
                    j = (m * i) - 1;
                    marks[j] = 1;
                }
            j = 0;
            }
            k++;    
        }
        /*Count the primes*/
        for (i = 0;i < n;i++) {
            if (marks[i] == 0) {
                nPrimes++; 
            }
        }

        primes = malloc(sizeof(int) * (nPrimes + 1));
        primes[0] = nPrimes;
        j = 1;
        for (i = 0;i < (n);i++) {
            if (marks[i] == 0) {
                primes[j] = num[i];        
                j++;
            }
        }
        free(num);
        free(marks);
        return primes;
    }

    int main(int argc, char **argv)
    {
        int i = 0;
        int n = 0;
        int *primes = 0;
        if (argc < 2) {
            printf("Need a number argument");
        } else if (atoi(argv[1]) == 1) {
            printf("Enter Num > 1");
        } else if (atoi(argv[1]) < 0) {
            printf("Enter a positive value");
        } else {
            n = atoi(argv[1]);
        }

        primes = eSieve(n);

        for (i = 0;i < primes[0];i++) {
            printf("%d, ", primes[i+1]);
        }
        printf("\nNumber of Primes: %d\n", primes[0]);
        return 0;
    }

Valgrind Output

==3970== Memcheck, a memory error detector
==3970== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==3970== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==3970== Command: ./sieve 1000
==3970== 
==3970== Invalid write of size 4
==3970==    at 0x400837: eSieve (sieve.c:34)
==3970==    by 0x4009EF: main (sieve.c:76)
==3970==  Address 0x5502fc4 is 4 bytes after a block of size 4,000 alloc'd
==3970==    at 0x4C2C74C: malloc (vg_replace_malloc.c:270)
==3970==    by 0x400777: eSieve (sieve.c:19)
==3970==    by 0x4009EF: main (sieve.c:76)
==3970== 
--3970-- VALGRIND INTERNAL ERROR: Valgrind received a signal 11 (SIGSEGV) - exiting
--3970-- si_code=1;  Faulting address: 0x105502FE0;  sp: 0x4030dad60

valgrind: the 'impossible' happened:
   Killed by fatal signal
==3970==    at 0x38061648: unlinkBlock (m_mallocfree.c:290)
==3970==    by 0x380620C3: vgPlain_arena_malloc (m_mallocfree.c:1607)
==3970==    by 0x38028474: vgMemCheck_new_block (mc_malloc_wrappers.c:263)
==3970==    by 0x3802860A: vgMemCheck_malloc (mc_malloc_wrappers.c:301)
==3970==    by 0x3809C800: vgPlain_scheduler (scheduler.c:1665)
==3970==    by 0x380AB9EC: run_a_thread_NORETURN (syswrap-linux.c:103)

sched status:
  running_tid=1

Thread 1: status = VgTs_Runnable
==3970==    at 0x4C2C74C: malloc (vg_replace_malloc.c:270)
==3970==    by 0x4008B1: eSieve (sieve.c:47)
==3970==    by 0x4009EF: main (sieve.c:76)


Note: see also the FAQ in the source distribution.
It contains workarounds to several common problems.
In particular, if Valgrind aborted or crashed after
identifying problems in your program, there's a good chance
that fixing those problems will prevent Valgrind aborting or
crashing, especially if it happened in m_mallocfree.c.

If that doesn't help, please report this bug to: www.valgrind.org

In the bug report, send all the above text, the valgrind
version, and what OS and version you are using.  Thanks.

Error Message:

sieve: malloc.c:2369: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.

Answer 1

I haven't checked the entire logic, but the following loop can be a problem.

for (i = 2; j < n; i++) {
  j = (m * i) - 1;
  marks[j] = 1;
}

You are first accessing marks[j] and then checking whether j < n.

Instead add a check.

for (i = 2; j < n; i++) {
  j = (m * i) - 1;
  if ( j < n )
    marks[j] = 1;
}

Answer 2

Here j could be larger than n in marks[j] = 1;, which may write to the control block of the allocated memory and leads to errors when malloc/free/realloc.

    for (i = 2; j < n; i++) {
        j = (m * i) - 1;
        marks[j] = 1;
    }

EDITED:

I would suggest you to change it into this:

    for (j = m * 2 - 1; j < n; j += m)
        marks[j] = 1;

Answer 3

You were trying to write at the memory location which isn't assigned to marks[].

This should solve the problem:

 for (i = 2; (j = (m * i) - 1) < n; i++) {
                    marks[j] = 1;
 }