0

I'm writing a code for the "Sieve of Eratosthenes" in C, which prints all the prime numbers up to n. Here's my code:

#include <stdio.h>  
#include <stdlib.h>
#include "input2.h"

int main() 
{
    int n = read_int();
    int length = n-1;

    int *block_of_memory = (int *)malloc(sizeof(int));


    for(int i = 2; i <= length; i++)
    {
        block_of_memory[i] = 1;
    }

    for(int i = 2; i*i <= length; i++)
    {
        if(block_of_memory[i] == 1)
        {
            for(int j = i*i; j < length; j = j+i)
            {
                block_of_memory[j] = 0;
            }
        }

    }

    for (int i = 1; i <= length; ++i)
    {
        if(block_of_memory[i] == 1)
        {
            printf("%d\n", i);
        }

    }



    print_prime(block_of_memory, length);

    free(block_of_memory);

    return 0;

}

I'm not sure what I'm doing wrong here. When I want all the prime uptown 5 (for example), I get:

Give a number: 5
1
1
4, 5,
SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
poppy_smoke
  • 1

1 Answers1

2

You're not allocating enough memory:

int *block_of_memory = (int *)malloc(sizeof(int));

should actually be:

int *block_of_memory = malloc(n * sizeof(int));

This way, you allocate space for the entire array of n ints, and not just one int. Also, never cast the result of malloc. In addition, your code has some logic errors:

for(int j = i*i; j < length; j = j+i)
{
    block_of_memory[j] = 0;
}

should actually be:

for(int j = i*i; j <= length; j = j+i)
{
    block_of_memory[j] = 0;
}

(notice the < length becomes <= length). This way, every element gets checked properly, including the element at length - 1.

Aplet123
  • 33,825
  • 1
  • 29
  • 55
  • I totally agree. Only luck would mean that this fixe the non-prime output though. – Yunnosch Nov 11 '20 at 15:16
  • @Yunnosch Oops! It turns out there was an edge case (when n - 1 is composite) that the code breaks on, and I didn't find it when testing my solution. Upon looking further, I found a bug and edited it into my answer. – Aplet123 Nov 11 '20 at 15:20
  • You show a solution and point out the differences. If you explain why they are necessary you can have my upvote. – Yunnosch Nov 11 '20 at 15:22
  • I tried your suggestions but it literally gave me the same output as before, – poppy_smoke Nov 11 '20 at 15:31
  • Really? Because I get the correct output with [this](https://pastebin.com/EasW4xwi) code. – Aplet123 Nov 11 '20 at 15:35
  • Rather than code a type in, use `block_of_memory = malloc(sizeof *block_of_memory * n);` to avoid mistakes. Also easier to review and maintain. – chux - Reinstate Monica Nov 11 '20 at 15:53