# Thread: How to use large numbers

1. ## 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, "%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 */ 2. Originally Posted by thecstudent
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
For starters, I suggest that you take a look at the GNU Multiple Precision Arithmetic Library. Download it and use it to extend your program with functionality #2. After you have it working fine and dandy, put it aside so that it can function as a reference implementation, i.e., you can use it to check if your program extended with your own arbitrary integer library implementation is working correctly. Originally Posted by thecstudent
Also, could you please take a look at my simple program and criticize it? I really want to learn the language!
Post code within bbcode tags as it makes reading code easier (assuming that you have good formatting to begin with). 3. As a small refinement, this loop
Code:
`for ( k = 2; k <= sr; k++ )`
... instead you can start at 5 and increment by 2. 4. /* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

Generalization: Any number that, when divided by n#, has a remainder of either 1 or a prime > n, is coprime to all primes <= n. Where # denotes primorial. 5. "millions of digits"?!?!
I'm researching this very problem right now for my own big-int class.
Do you realise that even with 100000 digits you typically require somewhere between days and decades of processing time to determine with only a high degree of certainty that it is prime? (I.e. still can't be absolutely sure).
If you're really interested in determinig primality of large numbers then you have a lot of research to do before you'll get anywhere at all. 6. theCstudent -- Welcome to the forum!

Always put your code between code tags so it can be read easily. Originally Posted by User Name: /* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

Generalization: Any number that, when divided by n#, has a remainder of either 1 or a prime > n, is coprime to all primes <= n. Where # denotes primorial.
Interesting - thanks. I didn't know prime numbers % 6 equaled either 1 or 5.

Can you expand on the Generalization part? I felt this blast of something zing by my head - I must have instinctively ducked, because it went right by me. Thanks User Name. 7. We'll use 5#(2*3*5=30) for the example. All numbers, n, indivisible by 2, 3, AND 5 will meet the condition "n % 30 equals either 1 or any prime more than 5 and less than 30".

The test is similar to the Sieve of Eratosthenes, in how it eliminates a set of numbers based on what they're divisible by. The example I gave eliminates all numbers divisible by 2, 3, or 5, so it is effectively the same as doing the first 3 steps of the Sieve of Eratosthenes.

EDIT: Actually, it would be make sense to give the example in the same way as the original:
Where he said:
"All known primes => 5, when divided by 6 have remainder of 1 or 5,"(To be precise, it should be "All know primes => 6", but the results are the same.)
for our example, we would say:
"All known primes => 30, when divided by 30 have remainder of 1, 7, 11, 13, 17, 19, 23, or 29" 8. Originally Posted by uggmini Although I do not know what that means, but I still hope to learn from learning
That's the spirit! 9. 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. 10. 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. 11. 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.) 12. 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). 13. 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. 14. 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. 15. 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. Popular pages Recent additions 