program for prime numbers in c language

[ASIFSHEHZAD25]

What is the minimum range of numbers which we need to go necessarily to check either a number is prime or not?(for all integers)

[weaknessforcats]

Think about it. The largest number that can divide into another number cannot be more than half as large since 2 is the lowest factor.

BTW: This is not a C++ question.

[ASIFSHEHZAD25]

I know that I must go till n/2 but I was asking for the minimum range,because I don`t want my loop to run so many times!
And its a programme on which I am working not c++

[weaknessforcats]

Just stop the loop if you get any factor at all. A prime number has only itself and one as factors. If you get to n/2 and no factors, you have a prime.

[donbock]

To determine if N is a prime number you only need to do trial divisions for potential factors up to the square root of N. However, don't call the sqrt() function -- instead, [after the trial division] stop if the square of the potential factor is greater than or equal to N.

If the purpose of your program is to determine if some arbitrary integer is prime then go ahead and use the trial-division algorithm. However, if your goal is to find all prime numbers less than some particular limit then you don't need to divide at all! Look up "sieve of Eratosthenes".

[swapnali143]

To check whether given number is prime or not use following code...

#include<stdio.h>
 
void main()
{
   int n, c = 2;
 
   printf("Enter a number to check if it is prime\n");
   scanf("%d",&n);
 
   for ( c = 2 ; c <= n - 1 ; c++ )
   {
      if ( n%c == 0 )
      {
         printf("%d is not prime.\n", n);
	 break;
      }
   }
   if ( c == n )
      printf("%d is prime.\n", n);
 
  getch();
}

[Banfa]

You could use that code but it is horribly inefficient.

It checks to see if the number is divisible by all the even numbers when having checked to see if it is divisible by 2 and it isn't it is by definition not divisible by any other even number. This is easy to avoid.

In a similar vain it checks to see if the number is divisible by all multiples of 3 when having checked to see if it is divisible by 3 and it isn't it is by definition not divisible by any other multiple of 3. This is also easy to avoid.

It checks all numbers up to n-1 to see if they are a divisor of n there by checking about squareRoot(n) times more numbers that is required. Also easy to fix.

These inefficiencies mean that if you were trying to check if 10007 is prime you would test 294 times more numbers than required to determine that it is prime (10005 instead of 34 (ish)).