view release on metacpan or  search on metacpan

lib/Math/Prime/Util.pm  view on Meta::CPAN

  # step to the next prime (returns 0 if not using bigints and we'd overflow)
  $n = next_prime($n);

  # step back (returns undef if given input 2 or less)
  $n = prev_prime($n);


  # Return Pi(n) -- the number of primes E<lt>= n.
  my $primepi = prime_count( 1_000_000 );
  $primepi = prime_count( 10**14, 10**14+1000 );  # also does ranges

  # Quickly return an approximation to Pi(n)
  my $approx_number_of_primes = prime_count_approx( 10**17 );

  # Lower and upper bounds.  lower <= Pi(n) <= upper for all n
  die unless prime_count_lower($n) <= prime_count($n);
  die unless prime_count_upper($n) >= prime_count($n);


  # Return p_n, the nth prime
  say "The ten thousandth prime is ", nth_prime(10_000);

  # Return a quick approximation to the nth prime
  say "The one trillionth prime is ~ ", nth_prime_approx(10**12);

  # Lower and upper bounds.   lower <= nth_prime(n) <= upper for all n
  die unless nth_prime_lower($n) <= nth_prime($n);
  die unless nth_prime_upper($n) >= nth_prime($n);


  # Get the prime factors of a number
  my @prime_factors = factor( $n );

  # Return ([p1,e1],[p2,e2], ...) for $n = p1^e1 * p2^e2 * ...
  my @pe = factor_exp( $n );

  # Get all divisors including 1 and n
  my @divisors = divisors( $n );
  # Or just apply a block for each one
  my $sum = 0; fordivisors  { $sum += $_ + $_*$_ }  $n;

  # Euler phi (Euler's totient) on a large number
  use bigint;  say euler_phi( 801294088771394680000412 );
  say jordan_totient(5, 1234);  # Jordan's totient

  # Moebius function used to calculate Mertens
  $sum += moebius($_) for (1..200); say "Mertens(200) = $sum";
  # Mertens function directly (more efficient for large values)
  say mertens(10_000_000);
  # Exponential of Mangoldt function
  say "lamba(49) = ", log(exp_mangoldt(49));
  # Some more number theoretical functions
  say liouville(4292384);
  say chebyshev_psi(234984);
  say chebyshev_theta(92384234);
  say partitions(1000);
  # Show all prime partitions of 25
  forpart { say "@_" unless scalar grep { !is_prime($_) } @_ } 25;
  # List all 3-way combinations of an array
  my @cdata = qw/apple bread curry donut eagle/;
  forcomb { say "@cdata[@_]" } @cdata, 3;
  # or all permutations
  forperm { say "@cdata[@_]" } @cdata;

  # divisor sum
  my $sigma  = divisor_sum( $n );       # sum of divisors
  my $sigma0 = divisor_sum( $n, 0 );    # count of divisors
  my $sigmak = divisor_sum( $n, $k );
  my $sigmaf = divisor_sum( $n, sub { log($_[0]) } ); # arbitrary func

  # primorial n#, primorial p(n)#, and lcm
  say "The product of primes below 47 is ",     primorial(47);
  say "The product of the first 47 primes is ", pn_primorial(47);
  say "lcm(1..1000) is ", consecutive_integer_lcm(1000);

  # Ei, li, and Riemann R functions
  my $ei   = ExponentialIntegral($x);   # $x a real: $x != 0
  my $li   = LogarithmicIntegral($x);   # $x a real: $x >= 0
  my $R    = RiemannR($x);              # $x a real: $x > 0
  my $Zeta = RiemannZeta($x);           # $x a real: $x >= 0


  # Precalculate a sieve, possibly speeding up later work.
  prime_precalc( 1_000_000_000 );

  # Free any memory used by the module.
  prime_memfree;

  # Alternate way to free.  When this leaves scope, memory is freed.
  use Math::Prime::Util::MemFree;
  my $mf = Math::Prime::Util::MemFree->new;


  # Random primes
  my($rand_prime);
  $rand_prime = random_prime(1000);        # random prime <= limit
  $rand_prime = random_prime(100, 10000);  # random prime within a range
  $rand_prime = random_ndigit_prime(6);    # random 6-digit prime
  $rand_prime = random_nbit_prime(128);    # random 128-bit prime
  $rand_prime = random_safe_prime(192);    # random 192-bit safe prime
  $rand_prime = random_strong_prime(256);  # random 256-bit strong prime
  $rand_prime = random_maurer_prime(256);  # random 256-bit provable prime
  $rand_prime = random_shawe_taylor_prime(256);  # as above


=head1 DESCRIPTION

A module for number theory in Perl.  This includes prime sieving, primality
tests, primality proofs, integer factoring, counts / bounds / approximations
for primes, nth primes, and twin primes, random prime generation,
and much more.

This module is the fastest on CPAN for almost all operations it supports.
This includes
L<Math::Prime::XS>, L<Math::Prime::FastSieve>, L<Math::Factor::XS>,
L<Math::Prime::TiedArray>, L<Math::Big::Factors>, L<Math::Factoring>,
and L<Math::Primality> (when the GMP module is available).
For numbers in the 10-20 digit range, it is often orders of magnitude faster.
Typically it is faster than L<Math::Pari> for 64-bit operations.

All operations support both Perl UV's (32-bit or 64-bit) and bignums.  If
you want high performance with big numbers (larger than Perl's native 32-bit
or 64-bit size), you should install L<Math::Prime::Util::GMP> and