Exploring Number Theoretic Algorithms
The study of numbers, primarily integers, is known as number theory. This branch attempts to create various theorems and proofs that educate us more about simple numbers based on a variety of distinct mathematical features. Because numbers are at the foundation of computer science, these number theory notions may be applied to a wide range of conventional computing tasks. To overcome these computational challenges, a range of integer characteristics explored in number theory are employed to create efficient and statistically sound algorithms.
In this blog, we'll see the most well-known number theory method and see how they're utilized to address real-world situations.
The Sieve of Eratosthenes
Sieve of Eratosthenes is an almost mechanical procedure for separating out composite numbers and leaving the primes. It was invented by the Greek scientist and mathematician Eratosthenes who lived approximately 2,300 years ago.
Due to the complexity of these numbers, many algorithms that can be used to generate prime numbers ranging from simple to complex computations, Sieve of Eratosthenes is used to generate Prime numbers of randomly generated or sequential numbered random numbers, testing in this study to find out which algorithm is better used for large primes in terms of tim
There are several algorithms for printing all prime numbers smaller than a given integer, but the optimized one of which being Eratosthenes' sieve. When n is less than 10 million, the Eratosthenes sieve is one of the most efficient approaches to locate all primes lower than n.
Finding primes in Range [1:n] using Sieve of Eratosthenes
Algorithm:
The algorithm is very simple: at the beginning we write down all numbers between 2 and n. We mark all proper multiples of 2 (since 2 is the smallest prime number) as composite. A proper multiple of a number x, is a number greater than x and divisible by x. Then we find the next number that hasn't been marked as composite, in this case it is 3. Which means 3 is prime, and we mark all proper multiples of 3 as composite. The next unmarked number is 5, which is the next prime number, and we mark all proper multiples of it. And we continued this procedure until we processed all numbers in the row.
In the following image you can see a visualization of the algorithm for computing all prime numbers in the range [1;16]. It can be seen that quite often we mark numbers as composite multiple times.
The idea behind is this: A number is prime, if none of the smaller prime numbers divides it. Since we iterate over the prime numbers in order, we already marked all numbers, who are divisible by at least one of the prime numbers, as divisible. Hence if we reach a cell and it is not marked, then it isn't divisible by any smaller prime number and therefore has to be prime.
Time Complexity: O(n log log n)
Space Complexity: O(n)
Code:
void SieveOfEratosthenes(int n)
{
bool prime[n + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for (int p = 2; p <= n; p++)
if (prime[p])
cout << p << " ";
}
Illustration:
Algorithm:
The method of testing prime number generator using the Sieve of Eratosthenes algorithm based on the steps previously described, here is the test to determine the primes of the numbers 1 – 100
1. First step show numbers 1 to 100
2. The second step, Removing the number 1 and multiples of 2 except the number 2 itself, the result show below
3. Third step, removing multiples of 3 except the number 3 itself
4. Fourth step, removing multiples of 5 except the number 5 itself
5. Fifth step, removing multiples of 7 except the number 7 itself
The end result of the Sieve of Eratosthenes algorithm process is as follows: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.
Sieve of Sundaram
Algorithm:
printPrimes(n)
[Prints all prime numbers smaller than n]
1) In general Sieve of Sundaram, produces primes smaller than
(2*x + 2) for a number given number x. Since we want primes
smaller than n, we reduce n-1 to half. We call it nNew.
nNew = (n-1)/2;
For example, if n = 102, then nNew = 50.
if n = 103, then nNew = 51
2) Create an array marked[n] that is going
to be used to separate numbers of the form i+j+2ij from
others where 1 <= i <= j
3) Initialize all entries of marked[] as false.
4) // Mark all numbers of the form i + j + 2ij as true
// where 1 <= i <= j
Loop for i=1 to nNew
a) j = i;
b) Loop While (i + j + 2*i*j) 2, then print 2 as first prime.
6) Remaining primes are of the form 2i + 1 where i is
index of NOT marked numbers. So print 2i + 1 for all i
such that marked[i] is false.
Code:
int SieveOfSundaram(int n)
{
int nNew = (n-1)/2;
bool marked[nNew + 1];
memset(marked, false, sizeof(marked));
for (int i=1; i<=nNew; i++)
for (int j=i; (i + j + 2*i*j) <= nNew; j++)
marked[i + j + 2*i*j] = true;
if (n > 2)
cout << 2 << " ";
for (int i=1; i<=nNew; i++)
if (marked[i] == false)
cout << 2*i + 1 << " ";
}
Illustration:
All red entries in the illustration below are marked entries. For every remaining (or black) entry x, the number 2x+1 is prime.
Lets see how it works for n=102, we will have the sieve for (n-1)/2 as follows:
Mark all the numbers which can be represented as i + j + 2ij
Now for all the unmarked numbers in the list, find 2x+1 and that will be the prime:
Like 2*1+1=3
2*3+1=7
2*5+1=11
2*6+1=13
2*8+1=17 and so on..
How does this work?
When we produce our final output, we produce all integers of the form 2x+1 (i.e., they are odd) except 2 which is handled separately.
Let q be an integer of the form 2x + 1.
q is excluded if and only if x is of the
form i + j + 2ij. That means,
q = 2(i + j + 2ij) + 1
= (2i + 1)(2j + 1)
So, an odd integer is excluded from the final list if
and only if it has a factorization of the form (2i + 1)(2j + 1)
which is to say, if it has a non-trivial odd factor.
Analysis between Sieve of Sundaram and Sieve of Eratosthenes:
The experiment to compare prime generator with Sieve of Eratosthenes and Sieve of Sundaram algorithms has found that for small prime numbers Sieve of Sundaram is better than Sieve of Eratosthenes; but to display a large prime number Sieve of Eratosthenes is better.
To prove this, random numbers were generated and determined the prime numbers from a random number by the algorithm Sieve of Eratosthenes and Sieve of Sundaram,
List Numbers
From the table above obtained graph of testing for the number of primes produced by using Sieve of Eratosthenes and Sieve of Sundaram algorithm as follows:
Time comparison graph
Hence, the graph explains the greater the number of primes produced then the sieve of Eratosthenes is better than the Sieve of Sundaram algorithm.
Extensions of Sieve
Sieving by the odd numbers only
Since all even numbers (except ) are composite, we can stop checking even numbers at all. Instead, we need to operate with odd numbers only.
First, it will allow us half the needed memory. Second, it will reduce the number of operations performed by the algorithm approximately in half.
bitset<500001> Primes;
void SieveOfEratosthenes(int n)
{
Primes[0] = 1;
for (int i = 3; i*i <= n; i += 2) {
if (Primes[i / 2] == 0) {
for (int j = 3 * i; j <= n; j += 2 * i)
Primes[j / 2] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (i == 2)
cout << i << ' ';
else if (i % 2 == 1 && Primes[i / 2] == 0)
cout << i << ' ';
}
}
Prime Factorization using Sieve
Explanation:
while( num ! = 1 ):
We keep on dividing it with its smallest prime factor.
The smallest prime factor is pre-calculated using a slightly modified prime sieve.
Since we start from 2 and go on, we mark the first multiple as the spf.
Preprocessing for Sieve: O(n log log n)
Time Complexity for factorization: O(log n)
Space Complexity: O(n)
Problems with the Simple Sieve:
The Sieve of Eratosthenes appears to be functional, however when n is big, the Simple Sieve encounters the following drawbacks.
An array of size (n) may not be able to fit in memory.
Even with a somewhat larger n, the basic Sieve is not cache friendly. The method traverses the array without regard for reference locality.
So to tackle these problems we have the Segmented Sieve
Segmented Sieve
Segmented Sieve first uses Simple Sieve to find primes smaller than or equal to √(n). The idea of this algorithm is to divide the range [0 ... n-1] in different segments and compute primes in all segments one by one.
The running time of block sieving is the same as for regular sieve of Eratosthenes (unless the size of the blocks is very small), but the needed memory will shorten to O(n+S) and we have better caching results.
Code:
int count_primes(int n) {
const int S = 10000;
vector<int> primes;
int nsqrt = sqrt(n);
vector<char> is_prime(nsqrt + 2, true);
for (int i = 2; i <= nsqrt; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (int j = i * i; j <= nsqrt; j += i)
is_prime[j] = false;
}
}
int result = 0;
vector<char> block(S);
for (int k = 0; k * S <= n; k++) {
fill(block.begin(), block.end(), true);
int start = k * S;
for (int p : primes) {
int start_idx = (start + p - 1) / p;
int j = max(start_idx, p) * p - start;
for (; j < S; j += p)
block[j] = false;
}
if (k == 0)
block[0] = block[1] = false;
for (int i = 0; i < S && start + i <= n; i++) {
if (block[i])
result++;
}
}
return result;
}
Linear Sieve
To discover all prime integers less than N, the traditional Sieve of Eratosthenes approach requires O(N log (log N)) time. A modified Sieve that works in O(N) time.
Algorithm:
For every number i where i varies from 2 to N-1:
Check if the number is prime. If the number
is prime, store it in a prime array.
For every prime numbers j less than or equal to the smallest
prime factor p of i:
Mark all numbers i*p as non_prime.
Mark smallest prime factor of i*p as j
Code:
void manipulated_seive(int N)
{
isprime[0] = isprime[1] = false ;
for (long long int i=2; i<N ; i++)
{
if (isprime[i])
{
prime.push_back(i);
SPF[i] = i;
}
for (long long int j=0;
j < (int)prime.size() &&
i*prime[j] < N && prime[j] <= SPF[i];
j++)
{
isprime[i*prime[j]]=false;
SPF[i*prime[j]] = prime[j] ;
}
}
for (int i=0; i<prime.size() && prime[i] <= N ; i++)
cout << prime[i] << " ";
}
Illustration:
isPrime[0] = isPrime[1] = 0
After i = 2 iteration :
isPrime[] [F, F, T, T, F, T, T, T]
SPF[] [0, 0, 2, 0, 2, 0, 0, 0]
index 0 1 2 3 4 5 6 7
After i = 3 iteration :
isPrime[] [F, F, T, T, F, T, F, T, T, F ]
SPF[] [0, 0, 2, 3, 2, 0, 2, 0, 0, 3 ]
index 0 1 2 3 4 5 6 7 8 9
After i = 4 iteration :
isPrime[] [F, F, T, T, F, T, F, T, F, F]
SPF[] [0, 0, 2, 3, 2, 0, 2, 0, 2, 3]
index 0 1 2 3 4 5 6 7 8 9
Applications of Sieve:
Prime generation in between 1 to n; O(nloglogn)
Generate divisor list of all the numbers in between 1 to n; O(nlogn)
To count the Number Of Divisor for all the numbers in between 1 to n; O(nlogn)
To find the Sum Of Divisor for all the numbers in between 1 to n; O(nlogn)
To find the number of co-primes for all the numbers in between 1 to n; O(nlogn)
Conclusion:
Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers.
Reference:
Prime Numbers Comparison using Sieve of Eratosthenes and Sieve of Sundaram Algorithm: D Abdullah et al 2018 J. Phys.: Conf. Ser. 978 012123
https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
https://cp-algorithms.com/algebra/prime-sieve-linear.html
Comments
Post a Comment