How can I make this very small C program faster?

Question

Is there any simple way to make this small program faster? I've made it for an assignment, and it's correct but too slow. The aim of the program is to print the nth pair of primes where the difference between the two is two, given n.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isPrime(int number) {
  for (int i = 3; i <= number/2; i += 2) {
    if (!(number%i)) {
      return 0;
    }
  }

  return 1;
}

int findNumber(int n) {
  int prevPrime, currentNumber = 3;

  for (int i = 0; i < n; i++) {   
    do {
      prevPrime = currentNumber;  

      do {                               
        currentNumber+=2;
      } while (!isPrime(currentNumber));

    } while (!(currentNumber - 2 == prevPrime));
  }

  return currentNumber; 
}

int main(int argc, char *argv[]) {
  int numberin, numberout;
  scanf ("%d", &numberin);

  numberout = findNumber(numberin);

  printf("%d %d\n", numberout - 2, numberout);
  return 0;
}

I considered using some kind of array or list that would contain all primes found up until the current number and divide each number by this list instead of all numbers, but we haven't really covered these different data structures yet so I feel I should be able to solve this problem without. I'm just starting with C, but I have some experience in Python and Java.

What are your constraints? Can you use precalculate array of primes pairs? An array of the first primes to speed up prime test? — Mathieu, Sep 16 '16 at 12:32
How much faster does it need to get? Do you need to reduce the big-O of your algorithm or is a constant facor good enough? — Klas Lindbäck, Sep 16 '16 at 12:32
Also you only need to test divsors from 1 < d < sqrt(N) ... You can calculate integer sqrt(N) by using the shift operator : sqrt(N) ~ `N >> 2`. — Ahmed Masud, Sep 16 '16 at 12:35
*Also you only need to test **prime divisors** from 1 < d < sqrt(N)* — David Pérez Cabrera, Sep 16 '16 at 12:37
@AhmedMasud `N >> 2` is the same as `N/4` which has nothing to do with the square root. — Klas Lindbäck, Sep 16 '16 at 12:40
I guess You should try [codereview](http://codereview.stackexchange.com/) ;) — Kamiccolo, Sep 16 '16 at 12:52
I'm voting to close this question as off-topic because it is a working program asking for performance improvements. — Daniel A. White, Sep 16 '16 at 13:02
@DanielA.White Questions on software algorithms are on-topic for SO. — Klas Lindbäck, Sep 16 '16 at 13:34
@DavidPérezCabrera *Also you only need to test prime divisors from 1 < d **≤** sqrt(N)*. — Will Ness, Sep 16 '16 at 22:56

vz0 · Answer 1 · 2016-09-16T13:09:18.063

To find pairs of primes which differ by 2, you only need to find one prime and then add 2 and test if it is also prime.

if (isPrime(x) && isPrime(x+2)) { /* found pair */ }

To find primes the best algorithm is the Sieve of Eratosthenes. You need to build a lookup table up to (N) where N is the maximum number that you can get. You can use the Sieve to get in O(1) if a number is prime. While building the Sieve you can build a list of sorted primes.

If your N is big you can also profit from the fact that a number P is prime iif it doesn't have any prime factors <= SQRT(P) (because if it has a factor > SQRT(N) then it should also have one < SQRT(N)). You can build a Sieve of Eratosthenes with size SQRT(N) to get a list of primes and then test if any of those prime divides P. If none divides P, P is prime.

With this approach you can test numbers up to 1 billion or so relatively fast and with little memory.

score 1 · Answer 2 · answered Sep 16 '16 at 12:38

1

Here is an improvement to speed up the loop in isPrime:

bool isPrime(int number) {
  for (int i = 3; i * i <= number; i += 2) {  // Changed the loop condition
    if (!(number%i)) {
      return 0;
    }
  }

  return 1;
}

answered Sep 16 '16 at 12:38

Klas Lindbäck

33,105
5
57
82

Thank you! I already thought of taking the square root of number, but I thought that only would take more time. Of this alternative I hadn't thought of. I try it and see if it's enough. – rvvermeulen Sep 16 '16 at 12:53
You only need to find the `sqrt` once for each number (not in every iteration), but the multiplikation is performed each iteration. So an efficient integer `sqrt` might be slightly faster (depending on what the optimiser can do). Integer sqrt is discussed here: http://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-square-root-algorithm-for-arm-thumb2 – Klas Lindbäck Sep 16 '16 at 13:10

score 1 · Answer 3 · edited May 23 '17 at 12:32

You are calling isPrime more often than necessary. You wrote

currentNummber = 3;
/* ... */
do {                               
   currentNumber+=2;
} while (!isPrime(currentNumber));

...which means that isPrime is called for every odd number. However, when you identified that e.g. 5 is prime, you can already tell that 10, 15, 20 etc. are not going to be prime, so you don't need to test them.

This approach of 'crossing-out' multiples of primes is done when using a sieve filter, see e.g. Sieve of Eratosthenes algorithm in C for an implementation of a sieve filter for primes in C.

chux - Reinstate Monica · Answer 4 · 2016-09-16T14:42:58.107

Avoid testing ever 3rd candidate

Pairs of primes a, a+2 may only be found a = 6*n + 5. (except pair 3,5).

Why?

a + 0 = 6*n + 5   Maybe a prime
a + 2 = 6*n + 7   Maybe a prime
a + 4 = 6*n + 9   Not a prime when more than 3 as 6*n + 9 is a multiple of 3

So rather than test ever other integer with + 2, test with

a = 5;
loop {
  if (isPrime(a) && isPrime(a+2)) PairCount++;
  a += 6;
}

Improve loop exit test

Many processors/compilers, when calculating the remainder, will also have available, for nearly "free" CPU time cost, the quotient. YMMV. Use the quotient rather than i <= number/2 or i*i <= number to limit the test loop.

Use of sqrt() has a number of problems: range of double vs. int, exactness, conversion to/from integer. Recommend avoid sqrt() for this task.

Use unsigned for additional range.

bool isPrime(unsigned x) {
  // With OP's selective use, the following line is not needed.
  // Yet needed for a general purpose `isPrime()`
  if (x%2 == 0) return x == 2;

  if (x <= 3) return x == 3;
  unsigned p = 1;
  unsigned quotient, remainder;
  do {
    p += 2;
    remainder = x%p;
    if (remainder == 0) return false;
    quotient = x/p;         // quotient for "free"
  } while (p < quotient);   // Low cost compare
  return true;
}

How can I make this very small C program faster?

4 Answers4