C program for prime number

On : 3:41 PM

To understand better please read the following post first, it will clear your concept of prime number What is prime number and Why 1 is not a prime number?


#include<stdio.h>

int main(){
    int n, i,check;
    printf("Enter a positive number\n");
    scanf("%d",&n);
    for(i=2;i<=n/2;i++){

        if(n%i==0) {
            check = 1;
            break;
        }
    }

    if(check==1)
        printf("\n%d is not a prime number\n",n);
    else
        printf("\n%d is a prime number\n",n);

    return 0;
}

Logic: The above program takes an integer n to check whether it is prime and use two control variables i & check Since every number is divisible by 1 so we started from i = 2. And i will be up to n/2. Why n/2 and why not n Because if we divide n, by any number between n/2 and n it will give us a remainder. For example if we divide 12 by 7(12÷2 < 7) it will remain 5, in case of 9 it will remain 3. That makes if(n%i==0) false every time. So if we take n it just increase time complexity.

Then we divide n with 2 to n/2 if it divide without any remainder, we set check = 1 And show it as not a prime.

Another one


#include<stdio.h>
int main(){
    int min, max, i,count;

    printf("Enter the first end point\n");
    scanf("%d",&min);
    printf("Enter the second end point\n");
    scanf("%d",&max);
    printf("\n\n");
    for(i=min;i<=max;i++){
        for(count=2;count<=i;count++){
            if(i%count==0) break;
        }
        if(count==i) printf("%d\n",count);
    }

    return 0;
}


Here we also use the same logic to find out the prime number from an interval.