factorize.c File Reference

Routines for prime factorization and primality testing. More...

#include "mdb.h"

Go to the source code of this file.

Functions
int64_t	is_prime (int64_t number)
	Determine if a number is prime.
int64_t	smallest_factor (int64_t number)
	Find the smallest prime factor of a number.
int64_t	next_prime_factor (int64_t *number)
	Extract the next prime factor from a number.
int64_t	largest_prime_factor (int64_t number)
	Find the largest prime factor of a number.

Detailed Description

Routines for prime factorization and primality testing.

Copyright

• (c) 2002 The University of Chicago, as Operator of Argonne National Laboratory.
• (c) 2002 The Regents of the University of California, as Operator of Los Alamos National Laboratory.

License

This file is distributed under the terms of the Software License Agreement found in the file LICENSE included with this distribution.

Author

M. Borland, C. Saunders, R. Soliday

Definition in file factorize.c.

Function Documentation

is_prime()

int64_t is_prime

(

int64_t

number

)

Determine if a number is prime.

Checks if the given number is prime.

Parameters

number

The number to test.

Returns

1 if the number is prime. Otherwise, returns a negative value which is the negative of the smallest prime factor of the number.

Definition at line 26 of file factorize.c.

{
  int64_t i, n;
 
  n = sqrt(number * 1.0) + 1;
  if (n * n > number)
    n--;
  for (i = 2; i <= n; i++)
    if (number % i == 0)
      return (-i);
  return (1);
}

largest_prime_factor()

int64_t largest_prime_factor

(

int64_t

number

)

Find the largest prime factor of a number.

Iteratively factorizes the given number to determine its largest prime factor.

Parameters

number

The number to factorize.

Returns

The largest prime factor of the number, or 1 if the number is 1 or no factorization is possible.

Definition at line 83 of file factorize.c.

                                             {
  int64_t factor, lastFactor;
  lastFactor = 1;
  while ((factor = next_prime_factor(&number)) > 1)
    lastFactor = factor;
  return lastFactor;
}

next_prime_factor()

int64_t next_prime_factor

(

int64_t *

number

)

Extract the next prime factor from a number.

Removes and returns the next prime factor from the given number, dividing it out of the number. Subsequent calls will continue to factorize the updated number.

Parameters

number

Pointer to the number to factorize. On return, this value is reduced by dividing out the factor.

Returns

The next prime factor if any, otherwise 1 if no further factorization is possible.

Definition at line 65 of file factorize.c.

                                           {
  int64_t factor;
  if ((factor = smallest_factor(*number)) > 1) {
    *number /= factor;
    while (*number % factor == 0)
      *number /= factor;
    return factor;
  }
  return 1;
}

smallest_factor()

int64_t smallest_factor

(

int64_t

number

)

Find the smallest prime factor of a number.

Returns the smallest prime factor of a given number. If the number is prime, returns the number itself.

Parameters

number

The number for which to find the smallest factor.

Returns

The smallest factor if found, or the number itself if it is prime. If the number is 1, returns 1.

Definition at line 46 of file factorize.c.

{
  int64_t i;
 
  if (number == 1)
    return (1);
  if ((i = is_prime(number)) == 1)
    return (number);
  return (-i);
}