prime.h File Reference

#include <cmath>
#include <random>
#include <vector>
#include <qx/math/prime.inl>

Go to the source code of this file.

Functions
template<class I >
std::vector< I >	qx::find_prime_factors (I nValue)
	Find all prime factors. More...
template<class I >
std::vector< I >	qx::find_primes (I nMaxNumber)
	Find all primes between 2 and nMaxNumber. More...
bool	qx::is_prime (size_t nValue)
	Is number prime. More...
bool	qx::is_prime (size_t nValue, double fProbability)
	Is number prime with some probability. More...

Detailed Description

Author

Khrapov

Date

6.08.2022

Copyright

(c) Nick Khrapov, 2022. All right reserved.

Definition in file prime.h.

Function Documentation

find_prime_factors()

template<class I >

std::vector< I > qx::find_prime_factors ( I  nValue )

inline

Find all prime factors.

Complexity:

O(sqrt(number))

Template Parameters

I	- Integral type

Parameters

nValue

- number for search

Return values

-	all prime factors vector

Definition at line 52 of file prime.inl.

find_primes()

template<class I >

std::vector< I > qx::find_primes ( I  nMaxNumber )

inline

Find all primes between 2 and nMaxNumber.

Sieve of Eratosthenes

Complexity:

O(nMaxNumber * log(log(number)))

Template Parameters

I	- Integral type

Parameters

nMaxNumber

- max number for search

Return values

-	all primes vector

Definition at line 102 of file prime.inl.

is_prime() [1/2]

bool qx::is_prime ( size_t  nValue )

inline

Is number prime.

1.0 probability, high computational complexity

Complexity:

O(sqrt(number))

Parameters

nValue

- number

Return values

-	true if prime

Definition at line 140 of file prime.inl.

is_prime() [2/2]

bool qx::is_prime ( size_t  nValue, double  fProbability  )

inline

Is number prime with some probability.

Parameters

nValue	- number
fProbability	- probability (0, 1]

Return values

-	true is number is prime with some probability

Definition at line 145 of file prime.inl.