Ok, here's my new program. I've removed a couple of libraries (math.h & stdlib.h), toned down my data types and simplified my math for this retarded child.
I can calculate approx 150% more prime numbers now without having to wait too long (ie: more than about 5 mins). The algorithm I'm using is extremely efficient, but creating a pointer with millions of elements is taxing.
Any ideas? I was thinking of using a random access file as storage instead of a pointer. I can probably reach the limits of 'int' that way! :-)
mw
Code:
#include<stdio.h>
#include<malloc.h>
/*
This program calculates prime numbers using the Eratosthenes Sieve algorithm. It will find the
prime numbers between 2 & "max". It overwrites the prime numbers to the file "prime_numbers.txt"
in the same folder.
Definitions:
1) Prime Number: a positive integer with only 2 divisibles (itself & 1); the number "1" is not
considered a prime number in this program
2) Composite Number: a number with more than 2 divisibles
Variable key:
highest = input from the user that is passed to "max"
max = the maximum range of prime numbers to calculate
prime[max] = a pointer array that stores all of the numbers in the "max" range
discard = this is used to calculate composite numbers
count = a variable I use to count with
An in-depth explanation of the Eratosthenes Sieve can be found on the internet.
*/
//prototypes
void start_prime (void);
int prime_calculator (int max);
int main (void)
{
start_prime ();
return 0;
}
void start_prime (void)
{
int highest;
do
{
//Input from user
printf ("\n\n*WARNING* Enter '0' to quit if you don't want to overwrite your output file!!");
printf ("\n\nPlease specify a max range to calculate prime numbers (up to 21,000,000).\n");
scanf ("%d", &highest);
//Weed killer
if (highest < 0 || highest == 1 || highest > 21000000)
{
printf ("\n(Setting max range to 100)\n");
highest = 100;
}
//Call prime_calculator function
if (highest != 0)
{
prime_calculator (highest);
}
} while (highest != 0);
printf ("\n");
}
int prime_calculator (int max)
{
int discard;
int count;
//Open and overwrite file for output
FILE *fp = fopen ("prime_numbers.txt", "w");
//Declare pointer array
int *prime = malloc ((max+1)*sizeof(*prime));
if (!prime)
{
puts ("\n\nERROR! Not enough Memory!\n\n");
return (0);
}
printf ("\nFinished declaring pointer array (step 1 of 4)...");
//Initialize pointer array
prime[0] = 0;
prime[1] = 0;
for (count = 2; count <= max; count++)
{
prime[count] = 1;
}
count = 0;
printf ("\n\nFinished initializing pointer array (step 2 of 4)...");
//Discard even numbers
for (discard = 4; discard <= max; discard = discard + 2)
{
prime[discard] = 0;
}
discard = 0;
printf ("\n\nFinished even discards (step 3 of 4)...");
//Discard remaining composite numbers using the Eratosthenes Sieve
count = 3;
do
{
for (discard = count * count; discard <= max; discard = discard + count * 2)
{
if (prime[discard] > 0)
{
prime[discard] = 0;
}
}
count++;
} while (count * count <= max);
count = 0;
discard = 0;
printf ("\n\nFinished the Eratosthenes Sieve (step 4 of 4)...");
//Output and closing for this function call
printf ("\n\nPrime Numbers between 2 and %d:\n", max);
if (max > 5500)
{
printf ("** Too many to print on screen! **");
}
for (count = 2; count <= max; count++)
{
if (prime[count] == 1)
{
if (max <= 5500)
{
printf ("%d ", count);
}
fprintf (fp,"\t%d", count);
}
}
count = 0;
max = 0;
free (prime);
fclose (fp);
printf ("\n\n");
return (0);
}
Originally Posted by Lionmane
