Printing all primes < 1,000,000 to a text file

Question

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

Answer 1

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 sieve-of-eratosthenes. It involves just addition, no division, and skips processing of numbers that are already known to be composite.

Answer 2

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.

Answer 3

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.