# Prime Generation and Manipulation

toggle TOC (ctrl + ⇔)

#### sal/algo/prime.h

Sieve | segmented sieve class that generates primes |
---|---|

.next_prime | next prime in the sequence or after a guess |

.closest_prime | the nearest prime to a guess |

.cur_prime | current prime in the sequence |

.nth_prime | nth prime, starting from 2(n=1) |

.primes_upto | sequence of primes up to a upper limit |

.is_prime | check if guess is a prime number |

.count | number of primes in sequence below current prime or an upper limit |

### Sieve of Eratosthenes ¶

Declaration

Parameters

init_limit | initial limit to sieve up to |

seg_size | the batch size that primes are generated in |

Example

Discussion

Its working mechanism is depicted in the image below, where multiples of first encountered primes are marked.
Although not the theoretical fastest prime generating algorithm (with complexity `O(nlglg(n))`

),
an optimized Sieve of Eratosthenes is computationally the fastest way to do so. The most important optimization
is to split the sieve into segments, the most efficient size being the L1 CPU cache. This vastly reduces cache
misses, but most importantly lifts the memory limit on the largest prime sievable. Supposing 4GB of free memory,
a traditional sieve using a 4GB large bit array (8 bits per byte) could only treat primes under 16 billion.

The implementation is influenced by primesieve, which boasts more extensive optimizations than SAL's, but I hope that my version is more readable and usable as part of larger projects.

### Next prime | `Sieve::`

next_prime¶

Declaration

Parameters

guess | a number immediately before the desired prime; returns the prime after if guess is a prime |

Example

Discussion

Often either a sequence of primes or a prime "next to" a number is needed. This method provides one means of doing so, the other one being closest_prime. Using next_prime to generate primes will result in uneven performance as the primes are sieved in segments at a time, with most of the work being at the boundary of a segment.

### Closest prime | `Sieve::`

closest_prime¶

Declaration

Parameters

guess | number around which a prime is wanted |

Example

Discussion

Primes often have use in information encoding due to its unfactorable nature. One application is finding acceptable sizes for hash tables. If the hash function is any number of Universal hashes, then the size should be a prime close to a power of two (such as Mersenee primes) to replace division with shifts and additions but also while reducing clustering.

### Current prime | `Sieve::`

cur_prime¶

Declaration

Example

Discussion

Current prime in the sequence.

### Nth prime | `Sieve::`

nth_prime¶

Declaration

Parameters

nth | prime index starting with 2(n=1), 3(n=2) |

Example

Discussion

Prime numbering starts with an index of 1; nth = 0 or nth < 0 returns 0, but beware of underflows if using an unsigned type such as size_t by default.

### Primes up to | `Sieve::`

primes_upto¶

Declaration

Parameters

lim | upper limit for largest prime |

Example

Discussion

Returns a reference to the internal prime vector. Note that the last member
is not guranteed to be the prime just under lim!
(it will be if lim is greater than internal limit prior to running)
A separate copy guranteeing the last element is not done as that would be very inefficient and unncessary.
If the last prime is too large, use `sieve.count(lim) - 1`

to retrieve index of the desired back.

### Check if prime | `Sieve::`

is_prime¶

Declaration

Example

Discussion

Accomplished by first filtering out smooth numbers (ones with small factors) then performing a binary search on existing primes or sieving up to the number;

### Count primes under | `Sieve::`

count¶

Declaration

Parameters

upper | upper limit for largest prime |

Example

Discussion

Counting primes is more efficient than generating them and then counting since a bit sieve is used for counting only (8 byte statuses in 1 byte). Counting will not increase the current prime index or load primes into the internal vector.