Find smallest prime number greater than given n

Question

I need to write a program which will find a prime number, greater than the given n.

Can it be done simpler?

#include <stdio.h>
int isPrime(int n)
{
 int i,j=0;
 for(i=1; i<=n; i++)
 {
 if(n%i == 0)
 j++;
 }
 if(j == 2)
 return 1;
 else if(j > 2)
 return 0;
}
int fun(unsigned int n)
{
 int i=n+1;
 while(1)
 {
 if(isPrime(i))
 break;
 i++;
 }
 return i;
}
int main(int argc, char **argv)
{
 printf("%d\n", fun(19));
 return 0;
}

• Ismael Miguel: If this is meant to run multiple times, you should use memoization (en.wikipedia.org/wiki/Memoization).

Answer 1

You can implement function isPrime to test primality in a little more efficient manner:

int isPrime(int n) // assuming n > 1
{
 int i,root;
 if (n%2 == 0 || n%3 == 0)
 return 0;
 root = (int)sqrt(n);
 for (i=5; i<=root; i+=6)
 {
 if (n%i == 0)
 return 0;
 }
 for (i=7; i<=root; i+=6)
 {
 if (n%i == 0)
 return 0;
 }
 return 1;
}

• RubberDuck: I like where you're heading, but there's no need for two separate loops if you're counting by six in each of them.
• barak manos: @RubberDuck: You can do it in a single loop, which will perform the same number of operations as those two separate loops (in fact, it will even perform a few more operations per iteration).
• David Z: If the goal is clarity of code, I think it makes sense to combine the two loops - fewer lines of code are easier to digest, and it also makes clear the relationship between the two numbers being tested at each iteration. Granted this is somewhat subjective.
• Guffa: Hm... The question was to make the code simpler, not more complicated, was it not? ;)

Answer 2

Simple is nice, but you can easily more than double the performance.

for(i=1; i<=n; i++)

There's no reason to loop the whole way up to n. If you've not found a multiple of n by time you've reached its square root, it's not prime.

var sqroot = sqrt(n);
for (i = 2; i <= sqroot; i++)
{
 //...

Answer 3

You can replace this:

if(j == 2)
 return 1;
else if(j > 2)
 return 0;

with this:

return j == 2;

---

fun is not a great name. What does this function do? It finds the smallest prime greater than n. It would be good to call it as such.

Also, you made this function take an unsigned int, but then you drop the unsigned qualifier in isPrime. It would be better to be consistent.

It might be a good idea to define a type alias for this:

typedef unsigned int prime_t;

So that later if you want to support larger numbers and need to change int to long, you will be able to make that change in one place instead of many.

Answer 4

You can exclude the two cases from the loop in isPrime that you already know will be true (1 and n), that way you can simply exit as soon as you find out that it's not a prime instead of counting all of them:

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

That makes the code not only simpler, but also more efficient.

(You don't actually have to loop all the way to n-1, but checking how far you actually need to loop makes the code more complicated, and the question was about simplicity.)

You can use the condition in the loop in the fun function, instead of breaking out of an infinite loop:

int fun(unsigned int n)
{
 while(!isPrime(++n));
 return n;
}

Answer 5

First of all, the code doesn't check for illegal arguments. What happenes if you pass a negative number? Here is a shorter version of your code (without adding the above mentioned check):

int is_prime(int num) {
 int sq_root = sqrt(num);
 for(int i = 2; i <= sq_root; i++) {
 if (num % i == 0) {
 return 0;
 }
 return 1;
}
int fun(int num) {
 do {
 num++; // you want to find a prime number greater than the argument 
 } while (!isPrime(num)); 
 return num;
}

The idea is to keep the code as readble as possible. I prefer to go for the do { ... } while(...); loop instead of while(!isPrime(++num)); because it makes the code easier to read.

There's this thing that got stuck to my mind: "Debugging code is twice as hard as writing it, so if you write code as cleverly as possible, you are, by definition, not smart enough to debug it".

I really recommend using comments before the function describing what it does and the logic behind it. It helps a lot when writing the code, and it helps people who read your code to understand the logic behind, or some bugs, if it is the case. Suppose you describe what your function does in comments, but the code does not reflect that, it's easier for somebody reading the code to find the mistake.

Also, as others have stated, choose appropriate names for the functions. Since we are at this chapter, you could also take a look at coding conventions. It's a little unpleasant for C programmers to read Camel notation names (isPrime).