C ben prímszám ellenőrzés?

Csak a legszükségesebb dolgokat írtam át, sok helyen lehetne javítani a kódon, de így legalább megérted mi a lényeg.

#include<stdio.h>

int main(void){

int c,i,d;

//feltesszük, hogy prím

bool prim = true;

scanf("%d",&c);

i=c;

while ( i != 0){

// printf("%d\n",i);

d=c%i;

// printf("dolog %d\n",d);

if (d == 0){

//osztható d-vel, így nem prím

prim = false;

printf ("oszthato %d\n",i);

}

i--;

}

//Kiírás

if(prim) printf("%d prímszám.\n",c)

else printf("%d NEM prímszám.\n",c)

}

Nem kell az összes számra leellenőrizni.

Ha egy c számról meg akarod tudni, hogy prím-e, akkor elegendő egy olyan ciklust csinálni, amely 2ről indul és maximum gyök c-ig ellenőriz vagy amíg nem akad olyan szám amivel osztható, mert akkor nem prím. Ha gyök c-ig nm volt ilyen akkor már nem is lesz.

Sőt igazából folyamatosan optimalizálódna, ha az összes előtte lévő prímszámot kiszámolná, mert akkor már csak azokkal kellene végigosztania :D

Persze az összköltség nagyobb lenne, de a konkrét számra szánt idő jelentősen csökkenne.