/* Zadatak 13:
Napiˇsite program koji uˇcitava prirodni broj n ≥ 2 i provjerava je li broj n prost, koriste´ci slijede´ci (Wilsonov) teorem:
“Prirodni broj n je prost, ako i samo ako je ostatak pri dijeljenju (n − 1)! s n jednak −1”, odnosno, jednak n − 1 (u
standardnom sustavu ostataka modulo n). Program treba ispisati n i odgovaraju´cu poruku.
Uputa: Nemojte izravno raˇcunati (n − 1)! kao broj, ve´c mnoˇzenja radite samo s ostacima modulo n.
Primjer: neka je n = 5, a ostatke faktorijela raˇcunamo, na primjer, od 1 prema n − 1 = 4. Onda je, redom, 1 = 1 mod 5,
2 · 1 = 2 mod 5, 3 · 2 = 1 mod 5, 4 · 1 = 4 mod 5. Zadnji ostatak je 4 = n − 1, pa je 5 prost broj. */

#include <stdio.h>
int prost(int n){
    int i, b= 1,o=1;
    for(i = 1; i < n; i++){
        b = o * i;
        o = b % n;
    }
    if (o == n-1) return 0;
    else return 1;
}

int main(void){
    int n;
    printf("unesi n: \n");
    scanf("%d", &n);
    if(n < 2){
        printf("nise unjeli dobar n!\n");
        return 1;
    }
    if(prost(n) == 0) printf("Broj %d je prost.\n", n);
    else printf("Broj %d nije prost.\n", n);
    return 0;
}