patterncMajor
Printing all primes < 1,000,000 to a text file
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:
primes.h:
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
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.
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.