9
\$\begingroup\$

It takes a long time to execute and the CPU usage for the executable is about 25% while it is executing. Any ideas on how to make this faster?

primes.c:

#include <stdio.h>
#include "primes.h"

/* COUNT will be how many numbers to
 * check and see if they are prime */
#define COUNT 1000000

int main(void)
{
  FILE *ftp;
  /* open the file for writing*/
  ftp = fopen("primes.txt", "w");

  printPrimes(ftp, COUNT);
  return 0;
}

primes.h:

#include <stdbool.h>

bool isPrime(int number)
{
  int i;
  for (i = 1; i <= number; i++)
  {
    /* if i is not 1 and i is not the number itself,
     * ...then, check to see if the number divided
     * by i has a remainder of 0 */

    /* If the number divided by i (i != 1 or itself
     * has a remainder of zero, return false
     * (the number is NOT prime */

    if (i != 1 && i != number && (number % i == 0))
    {
      return false;
    }

  }
    /* If number is NOT found to be NOT prime, return true */
      return true;
}

void printPrimes(FILE *ftp, int count)
{
  int number;
  /* is the prime number, the first prime, second, etc
   * that is the value the places variable holds */
  int place = 0;

  /* print all primes starting at true and going to count */
  for (number = 2; number <= count; number++)
  {
    /* if the number is prime */
    if (isPrime(number))
    {
    place++;
    /* print to number to the file*/
    fprintf(ftp, "%d. %d\n", place, number);
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – janos Dec 9 '15 at 12:40
  • \$\begingroup\$ How many cores do you have? \$\endgroup\$ – RBarryYoung Dec 9 '15 at 15:22
  • 1
    \$\begingroup\$ This answer stackoverflow.com/a/1134851/109122 demonstrates a highly optimized, wheeled Sieve of Eratosthenes, that can emit 300,000 primes a second in VB.net on old hardware. Also, it actually fully factors every number (which is unnecessary for finding primes) so i have no doubt that it could be rewritten in C to run even faster for your purposes. It is extensively commented, explaining most of the Sieve tricks in use. \$\endgroup\$ – RBarryYoung Dec 9 '15 at 15:46
28
\$\begingroup\$

You are doing brute-force trial division, and not particularly smartly. For example, you only need to test odd candidate factors up to sqrt(number).

When you want to find many prime numbers, a much better algorithm to use is the . It involves just addition, no division, and skips processing of numbers that are already known to be composite.

\$\endgroup\$
  • 2
    \$\begingroup\$ I didn't even think about Sieve of Eratosthenes. That's a good idea. Also, you're right, I do only need to test odd candidates. \$\endgroup\$ – user91656 Dec 8 '15 at 4:14
  • \$\begingroup\$ Also I could change: for (i = 1; i <= number; i++) to for (i = 1; i <= number; i = i + 2) \$\endgroup\$ – user91656 Dec 8 '15 at 4:17
  • 1
    \$\begingroup\$ @user91656, which is what 200_success said by "...only need to test odd candidate factors..." \$\endgroup\$ – Emz Dec 8 '15 at 6:10
  • \$\begingroup\$ @user91656 That loop would fail for a power of 2 (1024), that loop would fail to see any divisor. If you wanted to use that loop, you would have to check for n%2==0 above your loop. \$\endgroup\$ – Tyzoid Dec 8 '15 at 10:30
  • \$\begingroup\$ Lets' remember that '1' is NOT a prime number, so the loop, suggested by @user91656, needs to be tweaked slightly to start with 2 rather than 1 (and the code should be rejecting any user input that is < 2 \$\endgroup\$ – user3629249 Dec 9 '15 at 3:12
21
\$\begingroup\$

There are a few algorithms that might help you:

  1. The sieve of Eratosthenes is the most simple to implement, but not the most efficient (still more efficient than your algorithm though)

  2. The sieve of Atkin is a lot faster, but a bit harder to implement

  3. BPSW-primality test. You can test a number for not being prime with this test, but you're never actually a 100% sure. It is just very very likely that if a number passes this test, the number is prime. According to Wikipedia no known counterexample has been found yet even though the first 2^64 numbers have been tested. It is however very likely that a counterexample exists.

\$\endgroup\$
  • \$\begingroup\$ Thanks for telling me about these algorithms. I will try to implement them. \$\endgroup\$ – user91656 Dec 8 '15 at 4:33
  • 5
    \$\begingroup\$ @OP: Since the first 2^64 numbers have been tested, and you only need up to 2^20, you should be able to use the BPSW test with 100% confidence. \$\endgroup\$ – LarsH Dec 8 '15 at 15:33
  • 3
    \$\begingroup\$ The Sieve of Atkins is not a lot faster than the the Sieve of Eratosthenes, not even theoretically. Theoretically, a "correctly" optimized SoA could be slightly faster than an optimized SoE (the difference is something like O(log log n), but i have never seen this demonstrated in practice, nor any implementation anywhere on the internet that could demonstrate it. Even correct pseudo code of an optimized implementation is exceedingly rare. Also, BPSW is a single prime testing method, whereas the Sieves are prime range-finding methods, orders of magnitude faster at this kind of problem. \$\endgroup\$ – RBarryYoung Dec 9 '15 at 15:40
11
\$\begingroup\$

you could start by removing the c functions from the header file.

Suggest placing those c functions into the primes.c file.

If that is done, then the primes.h file can be eliminated or reduce to prototypes for the functions ( except the main() )

placing code, in C, in a header file is asking for problems, especially as the number of files in the project grows.

Header files are for:

1) function prototypes that need to be seen across multiple files,

2) extern statements to make data visible across multiple files

3) define new types, for instance enum struct union definitions. The actual declarations of those types (the actual data) needs to be in a *.c file.

4) each header file should have statements to the pre-processor step of the compiler so the contents of the header file can only be #included once in any one *.c file. Typically :

#ifndef UNIQUE_NAME 
#define UNIQUE_NAME 

and at end of the header file:

#endif 

though pragma once at the beginning of the header file also works

Note: UNIQUE_NAME should be:

1) all caps with root words separated by underscores

2) is usually the same as the name of the header file with the . replaced with an underscore. I.E. if the header file name is Primes.h then the UNIQUE_NAME would typically be: PRIMES_H

When calling the function: fopen(), always check (!=NULL) to assure the operation was successful. Suggest:

FILE *ftp = NULL;
/* open the file for writing*/
if( NULL == (ftp = fopen("primes.txt", "w") ) )
{ // then, fopen failed
    perror( "fopen for primes.txt for writing failed");
    exit( EXIT_FAILURE);
}

// implied else, fopen successful

I/O calls are very expensive, time wise. I suggest generating a table to contain the primes, then printing the table in as few I/O operations as possible.

\$\endgroup\$
  • 3
    \$\begingroup\$ Or as I like to call it, SCREAMING_SNAKE_CASE \$\endgroup\$ – Patrick Roberts Dec 8 '15 at 5:06
  • 1
    \$\begingroup\$ Specifically, the problem with defining functions in a primes.h is that if the header is included by both alpha.c and beta.c, then if you try to link alpha.c and beta.c together into an executable, then you will get an error about symbols being defined twice. \$\endgroup\$ – 200_success Dec 8 '15 at 5:37
  • 1
    \$\begingroup\$ In modern C it may make sense to have (small-ish) functions in the header file and declare them inline in order to allow better optimizations. The inlining per se may not even yield the most benefit, but having the code visible opens the door to better optimization for the compiler without having to do sophisticated LTO. (Besides, it has nothing to do with better performance; as I indicated, it may even harm performance to move the functions out of the header.) The I/O concern otoh is valid, but the typical printf call will not result in one ;-). \$\endgroup\$ – Peter A. Schneider Dec 8 '15 at 9:58
  • \$\begingroup\$ @PeterA.Schneider, those functions in the header file will 1) not be valid candidates for inlining 2) moving them out of the header is the correct way to handle the given scenario. \$\endgroup\$ – user3629249 Dec 9 '15 at 3:05
  • \$\begingroup\$ "will not be valid candidates for inlining" - -finline-functions and others seem to indicate that it may depend... \$\endgroup\$ – JimmyB Dec 9 '15 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.