Cryptography Reference
In-Depth Information
Now the number of primes found is reported, and a field of
ULONG
variables of
commensurate size is allocated.
for (count=i=1;i<=L;i++)
{
count += f[i];
}
if ((primes = (ULONG*)malloc ((size_t)(count+1) * sizeof (ULONG))) == NULL)
{
return (ULONG*)NULL;
}
The field
f[]
is evaluated, and all the numbers
2i+1
marked as primes are stored
in the field
primes
.If
N
≥
2
, then the number 2 is counted as well.
for (count=i=1;i<=L;i++)
{
if (f[i])
{
primes[++count] = (i << 1) + 1;
}
}
if (N < 2)
{
primes[0] = 0;
}
else
{
primes[0] = count;
primes[1] = 2;
}
free (f);
return primes;
}
To determine whether a number
n
is composite it is sufficient, according
to what we have said above, to institut
e
a division test that divides
n
by all
prime numbers less than or equal to
√
n
. If one fails to find a divisor, then
n
is
itself prime; the prime test divisors are given to us by the sieve of Eratosthenes.
However, this method is not practicable, since the number of primes that have
to be tested becomes rapidly too large. In particular, we have the
prime number
