می تونی اول برای 2 چک کنید.سپس عدد رو بر 2 تا نصف خودش تقسیم کنید.اگر بخش پذیر نبود اول است. (اگر تا نصف بخش پذیر نباشد بر بقیه هم بخش پذیر نیست)
پیاده سازی این الگوریتم ممکنه راههای مختلفی داشته باشه .این یکی از اونهاست:
#include<stdio.h>
int n,k,i=2,flag=0;
int main()
{
printf("Enter the number");
scanf("%d",&n);
if (n==2)
printf("Prime");
else
{
do
{
k=n%i;
if (k==0)
flag=1;
i=i+1;
}
while (i<n/2 && flag==0);
}
if (flag==1)
printf("Not prime");
else
printf("Prime");
}