Search code examples
calgorithmperformanceoptimizationprimes

Wrote a program to print prime numbers, How do I make it better?


I started learning C the previous day and I wrote a program to print within a given range. Minimum and Maximum of range is given by user.

#include <stdio.h>
int check(int number)
{
    if (number == 1)
    {
        return 0;
    }
    int count = 2;
    while (count < number)
    {
        if (number%count == 0)
        {
            return 0;
        }
        count++;
    }
    return 1;
}
void main()
{
    int i,min,max;
    printf("Enter start of range: ");
    scanf("%d",&min);
    printf("Enter end of range: ");
    scanf("%d",&max);
    for (i = min;i < max;i++)
    {
        if (check(i) == 1)
        {
            printf("%d\n",i);
        }
    }
}

I am getting the output as expected, but I want to know if there is any better way to return 0 if the number entered is 1 or not as it appears like duct tape code to me.

I inserted this block of code before the program goes through a while loop to check for numbers>1.

if (number == 1)
    {
        return 0;
    }

I am getting the output as expected but I want to know if there is a better way than just placing an if statement.

My question is different from the suggested question because I want to know if there is any better way to figure out if 1 is not a prime number. The suggested question was using an if statement, just like how I did. If statement was present in suggested question, I wanted to know any other alternatives that does not use the if statement to check for 1.

I find my question different from the suggested question.


Solution

  • [ a little late to the prime party]

    How do I make it better?

    Fix prime check

    check(0) reports true. check(any_negative) reports true. Both should report false.

    Much too slow

    check(n) iterates up to n times. A simple change would iterate at most sqrt(n) times. That is 10,000 times faster for large n.

    Iterate while the divisor is less than or equal to the quotient.

    int prime_check(int number) {
      if (number % 2 == 0) {
        return number == 2;
      }
      // Do not use divisor*divisor <= number as that overflows for a large prime.
      // Good compilers emit efficient code for number / divisor and
      // nearby number % divisor, doing both for the time cost of one.
      for (int divisor = 3; divisor <= number / divisor; divisor += 2) {
        if (number % divisor == 0) {
          return 0;
        }
      }
      return number > 1;
    }
    

    Questionable max

    I'd expect max to be part of the range that is tested.

      printf("Enter end of range: ");
      scanf("%d",&max);
      // for (i = min; i < max; i++)
      for (i = min; i <= max; i++)
    

    Yet this is a problem when max == INT_MAX.