AMCAT Coding Questions asked in Programming Section Prime Numbers

Program to print prime numbers between 1 to n

/**
 * C program to print all prime numbers between 1 to n
 */
#include <stdio.h>
int main()
{
    int i, j, n, isPrime; //isPrime is used as flag variable
    /* Reads upper limit to print prime */
    printf(“Find prime numbers between 1 to : “);
    scanf(“%d”, &n);
    printf(“nAll prime numbers between 1 to %d are:n”, n);
    /* Finds all Prime numbers between 1 to n */
    for(i=2; i<=n; i++)
    {
        /* Assume that the current number is Prime */
        isPrime = 1;
        /* Check if the current number i is prime or not */
        for(j=2; j<=i/2; j++)
        {
            /*
             * If i is divisible by any number other than 1 and self
             * then it is not prime number
             */
            if(i%j==0)
            {
                isPrime = 0;
                break;
            }
        }
        /* If the number is prime then print */
        if(isPrime==1)
        {
            printf(“%d is Prime numbern”, i);
        }
    }
    return 0;
}
?
Note: For checking whether a number is Prime or not we just need to check that the number should not be divisible by any number between 2 to n-1. Apart from that you can also check between 2 to n/2. Since any number more than (n/2)+1 cannot be exactly divided by n except self n.


Output

Find prime numbers between 1 to : 100

All prime numbers between 1 to 100 are:
2 is Prime number
3 is Prime number
5 is Prime number
7 is Prime number
11 is Prime number
13 is Prime number
17 is Prime number
19 is Prime number
23 is Prime number
29 is Prime number
31 is Prime number