/* Program utvrdjuje da li je uneti broj prost. */

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

int prost (int x)
{
  int i;

  if (x<=1) return 0;
  if (x==2) return 1;

  // paran broj veci od 2 nije prost
  if (x%2==0)
    return 0;

  for (i=3; i<=sqrt(x);i+=2)
    if (x%i==0)
      return 0;

  return 1;
}

int main()
{
  unsigned x;

  printf("Unesite prirodan broj za koji proveravate da li je prost.\n");
  scanf("%u",&x);

  if (prost(x))
    printf("%d je prost\n",x);
  else
    printf("%d nije prost\n",x);

  return 0;
}