Apakah mungkin untuk membuat kode C ini lebih kecil? Mencetak semua bilangan prima dari 0 hingga 1000.

C, 89 karakter

int i,p,c;for(i=2;i<1e3;i++){c=0;for(p=2;p<i;p++)if(i%p==0)c++;if(c==0)printf("%u\n",i);}

59 57 byte

Berdasarkan pada solusi @feersum tetapi pemeriksaan awal dapat dilakukan golf lebih lanjut

for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);

Diedit berdasarkan komentar Runer112

67 byte

Di C tidak ada alternatif nyata untuk divisi percobaan, tetapi tentu saja bisa sedikit golf.

for(int p=1,d;p++<999;d&&printf("%d\n",p))for(d=p;--d>1;)d=p%d?d:1;

Membutuhkan deklarasi awal C99, yang menghemat 1 byte.

(Saya menulis ini tanpa menyadari batasan ukuran pada bilangan bulat di C, jadi sepertinya tidak berguna untuk memperpendek kode.)

Pertama, kata tentang algoritma. Sebelum bermain golf kode Anda, Anda harus memikirkan strategi keseluruhan terbaik untuk mendapatkan hasilnya.

Anda sedang memeriksa primality dengan melakukan pembagian trial - pengujian setiap potensi pembagi pdari i. Itu mahal dalam karakter karena butuh dua loop. Jadi, menguji keutamaan tanpa loop kemungkinan akan menyimpan karakter.

Pendekatan yang sering lebih pendek adalah dengan menggunakan Teorema Wilson : angkanya nprima jika dan hanya jika

fact(n-1)%n == n-1

di mana factfungsi faktorial. Karena Anda menguji semua kemungkinan ndari 1hingga 1000, mudah untuk menghindari penerapan faktorial dengan melacak produk yang sedang berjalan Pdan memperbaruinya dengan P*=nsetelah setiap loop. Inilah implementasi Python dari strategi ini untuk mencetak bilangan prima hingga satu juta.

Atau, fakta bahwa program Anda hanya memiliki hingga 1000 membuka strategi lain: tes primitif Fermat . Bagi sebagian orang a, setiap perdana nmemuaskan

pow(a,n-1)%n == 1

Sayangnya, beberapa komposit njuga lulus tes ini a. Ini disebut pseudoprim Fermat . Tetapi, a=2dan a=3jangan gagal bersama sampai n=1105, jadi cukuplah untuk tujuan Anda memeriksa bilangan prima sampai 1000. (Jika 1000 bukan 100, Anda hanya bisa menggunakan a=2.) Jadi, kami memeriksa primality dengan (kode ungolfed)

pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1

Ini juga gagal mengenali bilangan prima 2 dan 3, jadi mereka harus menggunakan casing khusus.

Apakah pendekatan ini lebih pendek? Saya tidak tahu karena saya tidak kode dalam C. Tapi, itu adalah ide yang harus Anda coba sebelum Anda menyelesaikan sepotong kode untuk mulai menambah karakter.

78 77 karakter

(Hanya menerapkan beberapa trik yang dipelajari dalam bahasa lain.)

int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}

76 karakter dalam mode C99

for(int i=0,p,c;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}

58 karakter (atau 61 untuk program lengkap)

Penggunaan kembali jawaban saya untuk pertanyaan serupa .
EDIT : sepotong kode yang berdiri sendiri, tidak ada fungsi untuk memanggil.

for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));

Program lengkap:

n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}

67 64 byte

Terinspirasi oleh solusi Alchymist:

int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}