Holden,
I understand that you wish to find some kind of formula to check if an integer is a prime number, but the nature of primes (and factorization of integers) makes this highly unlikely. An integer that is prime will only have itself as a factor.
Do you see how
finding the square root of a number by hand (the long way) would help find the integer part of the square root? This in turn would help in that you would know when the number is prime once testing all primes up to the integer part of the square root of this number.
The "sra" programs, when compiled and run, were created not so much to find the square root, which it does fine, but, paradoxically, to TEACH a human animal how to do this with paper and pencil.
This program, named hfac, lists the prime factors of a given integer:
/* These are the simplified steps to find all prime factors:
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n.
While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
void primeFactors(int n);
int main(int argc, char *argv[])
{
int i, h;
for(i=1; i<argc; i++) {
h = atoi( argv[
i ] ) ; // underlined i else this editor reads
primeFactors(h); // BBcode "italics"
printf("\n");
}
return 0;
}
void primeFactors(int n)
{
int i;
printf("%d: ", n);
while (n%2 == 0)
{
printf("%d ", 2);
n = n/2;
}
for (i = 3; i <= sqrt(n); i = i+2)
{
while (n%i == 0)
{
printf("%d ", i);
n = n/i;
}
}
if (n > 2)
printf ("%d ", n);
}
/* How does this work?
The steps 1 and 2 take care of composite numbers and step 3 takes care of prime numbers. To prove that the complete algorithm works, we need to prove that steps 1 and 2 actually take care of composite numbers. It is clear that step 1 takes care of even numbers. And after step 1, all remaining prime factor must be odd (difference of two prime factors must be at least 2), this explains why i is incremented by 2.
Now the main part is, the loop runs until square root of n. To prove that this optimization works, let us consider the following property of composite numbers.
Every composite number has at least one prime factor less than or equal to square root of itself.
This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than √n, then a * b > √n * √n, which contradicts the expression “a * b = n”.
In step 2 of the above algorithm, we run a loop and do following in loop
a) Find the least prime factor i (must be less than √n,)
b) Remove all occurrences i from n by repeatedly dividing n by i.
c) Repeat steps a and b for divided n and i = i + 2. The steps a and b are repeated till n becomes either 1 or a prime number.
Thanks to Vishwas Garg for suggesting the above algorithm.
*/
EXAMPLE:
mwh@coyote:[~]:
$ ----> hfac 987654321
987654321: 3 3 17 17 379721