HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMajor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
fileprimesall000textprinting

Problem

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 
#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 

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

Solution

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.

Context

StackExchange Code Review Q#113238, answer score: 28

Revisions (0)

No revisions yet.