まず gcc が入っていなければ、
$ sudo apt-get install build-essential
で入れておく。
eratosthenes.c をコンパイルしたかったら、まず cd でファイルのあるディレクトリに移り、
$ gcc eratosthenes.c
でコンパイルされる。コンパイルに成功すると常に a.out というファイルが作られるので、
$ ./a.out
で実行。実行ファイルをちがった名前にしたければ、-o オプションを使って
$ gcc -o eratosthenes eratosthenes.c
などとやれば eratosthenes ファイルができるので、あとは上と同じように最初に ./ を付けて実行。
参考：
gcc で C/C++ - L'Isola di Niente
Ubuntuで C言語を使おう | 不定期ソフトウェア開発
※追記
標準ライブラリを使うときは -lm オプションを付けるが、Linux Mint（Ubuntu）の場合はなぜかオプションを最後に付けないといけない。（2016/8/13）
$ gcc eratosthenes.c -lm
