Get a limit number to test all the prime numbers it contains in C

Question

My task was:

Write a program that accepts an integer as input and then displays all the prime numbers smaller than or equal to that number.

And my code is:

#include <stdio.h>
void FindPrime(int number);

int main()
{        
    int userInput, counter;
    printf("Please enter a limit number to test all the prime numbers it contains:\n");

    scanf("%d", &userInput);

    printf("The prime numbers %d contains are:\n", userInput);

    for (counter =  2; counter < userInput; counter++)        
    {
        FindPrime(counter);
    }

    return 0;
}

void FindPrime(int number)    
{
    int numberTest, nextNumber = 1;

    for (numberTest = 2; numberTest < number; numberTest++)
    {
        if (number%numberTest == 0 && numberTest < number)
            continue;
        else 
            nextNumber++;                
    }

    if (nextNumber == (number - 1))
        printf("%d ", number);
}

Can this code be improved?

Answer 1

• Personally, I would put FindPrime above main, to avoid having to declare it.

• Only have one variable declaration per line. With more than one, it becomes harder to see where a variable comes from. It doesn't really matter with a short program, but will for more complex ones.

• Your print statements contain text which contradict what the task says (contains rather than less than)

• userInput needs to be validated - Make sure that the user has entered a number, and it's greater than 0.

• As mentioned, it's better that a function does one thing, rather than multiple. So your FindPrime function should be responsible for finding one, and the caller should be responsible for printing it.

• In FindPrime, the if statement contains a condition that's already been tested for in the for loop, so you can simplify the if condition by removing it.

• Always use {} for if (and while, for etc) statements, even if they're single line. Sooner or later, you'll add another line and break things, causing a very subtle error. And in this example, I'd reverse the condition, since the normal case doesn't do anything.

  if (number%numberTest != 0 )
  {
      nextNumber++;
  }
  

With regards to the algorithm, it can certainly be improved, but that may be out of your reach at the moment.

Answer 2

To see if a number is prime, you only need to check that the number is divisible by any number between 2 and number+1/2. Cause if the number is divisible by any number between 2 and number+1/2 then it will also have the corresponding factor between between number+1/2 and number.

Consider a number, say 32.

(32+1)/2=16

To check that it is prime or not you only need to check if it is divisible by any number between 2 and 16 (inclusive).

So you need to change this line in your FindPrime(int number) function.

for (numberTest = 2; numberTest < number; numberTest++)

To

for (numberTest = 2; numberTest < (number+1)/2; numberTest++)

Secondly, you should the main function to call a function which checks whether the number is prime or not, if it is, then use main to print that number. It'll make your code clean since only main will print out and not the FindPrime function.

Here is my code :

#include<stdio.h>

int is_prime(int n);

void main(void) {
    int i, input;
    scanf("%d", &input);
    printf("The prime numbers %d contains are:\n", input);
    for(i = 2; i <= input; ++i) {
        if(is_prime(i)) {
            printf("%d\n", i);
        }
    }
}

int is_prime(int n) {
    int i;
    for(i=2; i <= (n+1)/2; ++i) {
        if(!n%i) {
            return 1;
        }
    }
    return 0;
}