Thread: How to use large numbers

Hello Team (Hellow World?),

I am a new C learner, I am trying to learn the language on my own, which it does not look too bad with the tutorials on this site.

I wrote a simple program to determine the primality of a number.
I wanted to extend my program to handle very large numbers.
Sure I can go on the web and find a number of routines already written, but I will not learn.

I want to modify the program, which I will list below, to:

1. Handle very large numbers with millions of digits
2. Use pointers to create a list of prime numbers as the program finds them

Also, could you please take a look at my simple program and criticize it? I really want to learn the language!

Thank you


/* This program will check a number for primality */
/* It expects 1 argument, an integer, positive number greater than 1 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int check4prime(int p); /* Prototype function */

int main(int argc, char *argv[])
{
int n;

if (argc != 2) exit(EXIT_FAILURE); /* Need at least 2 args */

sscanf(argv[1], "%d", &n); /* Convert String to int */

if ( check4prime(n) ) /* if 1 is returned, we found a prime */
{
/* It is prime */
printf("%d is prime!\n", n);
exit(EXIT_SUCCESS);
} /* End if */

} /* End of main */

/* ################################### */
/* Function to check for primality */
/* ################################### */

int check4prime(int p)
{
if ( p <= 1 ) return 0; /* Prime can't be <= 1 */
if ( p == 2 || p == 3 ) return 1; /* first 2 prime numbers */

int rem = p % 2; /* No even #, except 2, is known to be prime */
if ( rem == 0) return 0; /* Eliminate even # first */

/* If we are here, that means the number is odd and it is neither 2 nor 3 */
/* Can it be prime? */
/* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

rem = p % 6; /* Possible prime have rem = 1 or 5 */
if ( rem == 1 || rem == 5 ) /* Possible prime? */
{
/* So far, so good */
/* Continue checking for primality */

int k;
int sr = sqrt(p); /* No need to check behind sqrt(p) */

for ( k = 2; k <= sr; k++ ) {
if ( p % k == 0 )
{
return 0; /* False */
}
} /* for */

return 1; /* True, found a prime */
}
return 0; /* True, found a prime */
} /* End of check4prime */

As a small refinement, this loop

Code:

for ( k = 2; k <= sr; k++ )

... instead you can start at 5 and increment by 2.

On low numbers, this won't speed up your search for a prime, but on large numbers, it surely will help a lot:

"All prime numbers, are numbers that will not divide evenly by any other prime number, of lesser value."

That seems obvious, since primes will not divide evenly by any number except 1, but to use the above, in a program avoids ALL the testing of numbers against the candidate prime number, except for the prime numbers you've already found, of lesser value.

Say I want to test 10001 to see if it's a prime number. Instead of testing (starting the testing with 7):
7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101. 48 tests in all.

You only wind up testing:
7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 37, 39, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101. 27 tests in all.

As the number go higher, and primes become more widely separated (on average), that reduction in testing becomes greater.

I used an array to hold these lesser primes, but for the high range of primes you want to work with, that wouldn't be practical to hold all of them. You could hold a lot of them though.

In the realm of "mathematically intuitive and simple" code, it makes for a quick program - the first 12,000 prime numbers are found in 0.11 seconds on one thread of a 2.66 C2D cpu. It won't compare with the math intense ultra speedsters, but it's a lot faster than the less elegant, normal prime program, you see on the net so frequently.

The test is only probabilistic. Any number indivisible by 2, 3, and 5 will pass the example test. In other words, it fails for most multiple of 7 and higher primes

Not only that, but its effectiveness decreases as the numbers being tested increase.

Originally Posted by User Name:

The test is only probabilistic. Any number indivisible by 2, 3, and 5 will pass the example test. In other words, it fails for most multiple of 7 and higher primes

Not only that, but its effectiveness decreases as the numbers being tested increase.

? All the tests in this thread have been exact. (And the only multiple of 7 that is prime is 7, which passes.)

Originally Posted by User Name:

The way I recommend you use it, is to do something like this:

Code:

for(int i = 1;i <= limit;i++)
{
     primetest(6 * i + 1);
     primetest(6 * i + 5);
}

Which will only produce numbers indivisible by 2 and 3. In effect, this eliminates 2/3 of all numbers.

tabstop: 49 % 30 = 19, 49 is not prime, yet it passes the test. I meant that most multiples of 7, or of any prime higher than 7, such as 11 will pass the test. 77 % 30 = 17, which means it also passes the test, but is obviously not prime(7*11).

Gotcha, I see what you mean. Yes, it should be used to generate candidates.

A 2/3rd's reduction in testing sounds good, but it's really not that great.

Between 1 and 1,000, using only the previously generated prime numbers to test, you would reduce testing by 83% (there are 168 primes in the range).

As you go to larger numbers, the reduction would soar. For example, there are only 81 primes between 100,000 and 101,000, or 8 percent primes, a 92% reduction in testing.

Your suggestion offers no further reduction in testing at higher numbers.

I already said its effectiveness decreases exponentially for large numbers. But are you really going to argue that checking all 1000 numbers to find 81 primes is better than checking 333 numbers and still finding the same primes? Even though it isn't conclusive, it still reduces the set of numbers you have to test by a significant amount.