CODEWITHSUNDEEP
cperformanceloopsprimes
rvvermeulen
rvvermeulen

Reputation: 168

How can I make this very small C program faster?

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.

Upvotes: 2

Views: 231

Answers (4)

chux
chux

Reputation: 153338

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;
}

Upvotes: 0

vz0
vz0

Reputation: 32923

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.

Upvotes: 2

Frerich Raabe
Frerich Raabe

Reputation: 94289

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.

Upvotes: 1

Klas Lindb&#228;ck
Klas Lindb&#228;ck

Reputation: 33273

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;
}

Upvotes: 1

Related Questions