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

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?

-

• 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.

-
"Personally, I would put FindPrime above main, to avoid having to declare it." That remark is rather pointless, since proper program design wouldn't place these functions together with main() at all, they would be in a separate module prime.h + prime.c. Apart from that, I completely agree with everything stated. –  Lundin Jan 30 '13 at 15:53

To see if a number is prime, you only need to check that the number is divisible by any number between 2 and Square root of number. Cause if the number is divisible by any number between 2 and sqrt(number) then it will also have the corresponding factor between between number+1/2 and sqrt(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 < sqrt(number) + 1; 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>
#include <math.h>

int is_prime(int n);

int 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);
}
}
return 0;
}

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

-
Spoiler: there is no need to ever test if even numbers are prime, all even numbers are divisible by 2. Also, why did you suddenly change to void main()? There is nothing in the original post indicating that the code is intended for embedded systems. –  Lundin Jan 30 '13 at 15:50
To see if n is prime, it is enough to look for factors up to the square root of n. Actually, it is enough to test all primes up to the square root of n because every composite number has a prime factorization. –  Julian Maicher Jan 30 '13 at 19:48